Thread: Need help creating prime number program

I have an assignment saying I need to use the Sieve of Eratothenes to figure out which nubmers are prime from 1-499.

"One method for finding all prime numbers in the range from 1 - n is known as the Sieve of Eratosthenes. Consider the list of numbers from 2 - n. Two is the first prime number, but the multiples of 2 (4,6,8,...) are not, and so they are crossed out in the list. The first number after 2 that was not crossed out is 3, the next prime. We then cross from the list all higher multiples of 3 (6,9,12,...). The next number not crossed out is 5, the next prime, and so we cross out all higher multiples of 5 (10,15,20,...). We repeat this process until we reach the first number in the list that has not been crossed out and whose square is greater than n. Use the Sieve of Eratosthenes to list all prime numbers less than or equal to 499.


· Use a constant M = 499

· Use an array of boolean

· The output should be formatted so that each line (except possibly the last) contains exactly 10 primes"

I'm thinking set every element to true. Then, if it is a multiple of 2, make it false, if it is a multiple of 3 make it false... and so on.

I tried

Code:

for(int i = 1; i <= M; i++)
		prime[i] = true;						

	for(i = 2 ; i <= M; i++)					
		for(int j = 1; j <= M; j++)		
			if(j % i == 0 ) prime[j] = false;

But that makes every j value that is divisible by the i value false.... so when a prime is divided by itself, it turns to false.

Any suggestions?

I'm thinking set every element to true. Then, if it is a multiple of 2, make it false, if it is a multiple of 3 make it false... and so on.

Exactly, but you must remember that if an element has been marked false, it will always remain false and need not be checked again.

But that makes every j value that is divisible by the i value false.... so when a prime is divided by itself, it turns to false.

Why not add a simple check to see if i != j ?

Originally Posted by Spidey

Why not add a simple check to see if i != j ?

Oh my god, I feel like an idiot. That fixed it ha ha... Thanks! Hurray for wasting a thread!