 KMN -4 years ago 52
Java Question

# Sieve of Eratosthenes will not sieve Prime Numbers

For an assignment I am doing for one of my classes, we have to implement a Sieve of Eratosthenes. I have tried seven times to get a code that works and have tried incorporating numerous solutions I've researched. I finally have one that will output numbers. Unfortunately, it prints both composite and prime numbers, and doesn't print 2.

My code is as follows:

``````public class EratosthenesSieveAttempt6 {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
int limit;

System.out.print("Please enter the highest number to check "
+ "(number must be greater than 2): ");

limit = keyboard.nextInt();

while (limit <= 2){
System.out.println("Error - number must be greater than 2.");
System.out.println("Please enter the highest number to check: ");
limit = keyboard.nextInt();
}

boolean[] numbers = new boolean[limit + 1];
int newPrime = 2;

for(int i = 0; i < limit + 1; i++){
numbers[i] = true;
}

for(int j = 1; j < limit + 1; j++) {
if (j % 2 == 0) {
numbers[j] = false;
}

for(int k = j + 1; k < limit + 1; k++) {
if(numbers[k] == true){
j = k;

System.out.println(k);
}
}
}
}
}
``````

I'm suspecting that there is a problem with my loops. I fixed the
`i`
and
`j`
variables for my first two loops so that it would print out from 2 onward, the problem seems to be that it's not marking the composite numbers as false after I've initialized the array to
`true`
.

Thank you in advance for your help. Mohsen_Fatemi
Answer Source

first you have an array , you named it numbers , each index of this array shows that the number is prime or not , if it is prime the value is `true` otherwise `false` , look you know `2` is prime , then it's multiplications are not prime

4 , 6 , 8 , 10 , 12 , 14 , ...

after you flagged these as `false` , you must go to the next number `3` is prime so

6 , 9 , 12 , 15 , ...

are not prime and must be flagged as `false`

then the next number would be `5` and so on , you have to do this with `i` and `j` variables

``````    boolean[] numbers = new boolean[limit + 1];
int newPrime = 2;

for(int i = 2; i < limit + 1; i++){
numbers[i] = true;
}
for(int i = 2 ; i < limit+1 ; i++){
if(numbers[i]){
for(int j = i+i ; j < limit + 1 ; j+=i)
numbers[j] = false;
}
}
``````

and you can print the result :

``````for(int i = 0 ; i < limit+1 ; i++)
if(numbers[i])
System.out.print(i+"   ");
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download
Latest added