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?