KMN 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.

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