Can someone please explain how this implementation works? Also, can it be made better? How?

Question

public class Main { 
    public static void main(String args []){ 
        long numberOfPrimes = 0; //Initialises variable numberOfPrimes to 0 (same for all other variables)
        int number = 1; 
        int maxLimit = 10000000; 
        boolean[] sieve = new boolean[maxLimit]; //creates new boolean array called sieve and allocates space on the
                                                //stack for this array which has maxLimit spaces in it 
        for ( int i = 2; i < maxLimit; i++ ) { //for statement cycling from 2 to 10000000, does not execute the rest
                                              //of the block if the boolean value in the array is true 
            if ( sieve[i] == true ) continue; 

            numberOfPrimes++; //otherwise it increments the number of prime numbers found

            if ( numberOfPrimes == 10001 ) {  //if 10001st prime number is found, break from loop
                number = i; 
                break; 
            } 

            for ( int j = i+i; j < maxLimit; j += i ) //do not understand the point of this loop logically
                sieve[j] = true;                      //testing if the value in the array is true again?
        } 
        System.out.println("10001st prime: "+ number); 
    } 
    }

I don't really understand what is going on in this program and was hoping somebody could explain it to me? I have commented the specific lines causing me trouble/what I understand lines to be doing. Thank you very much for all the help! :)

Answer 1

Make yourself familiar with Eratosthenes' Sieve algorithm. Wikipedia even has animated gif demonstrating the process. And your code is just a straightforward implementation of it.

Answer 2

The loop in question isn't checking for true values, it's setting true values.

It's going through each multiple of the prime and marking it as non-prime up to maxLimit. You'll notice there's no other math in the code to determine what's prime and what's not.

Answer 3

This is the algorithm to find the prime numbers between 1 and the maximum limit given.

And the loop added 2nd is to make true for the number which is divisible by any other number. so for the first outer loop all the number divisible by two ll be set to true then divisible by 3 then by 4 and so on.. and the numbers for which the boolean array contains false are the prime numbers.

Answer 4

for ( int j = i+i; j < maxLimit; j += i ) //dont understand the point of this loop logically
                sieve[j] = true;          //testing if the value in the array is true again ?

This is not a testing, but rather a setting. This loop is setting all the items in the array with indexes multiple of i to true. When i is 2, then the items 4, 6, 8 ... will be set to true. When i is 3, the items 6, 9, 12 ... will be set to true and so on.

And as you can deduce by the first if,

if ( sieve[i] == true ) continue; 

... all the items that are true correspond to non-prime numbers.

Answer 5

Yes, this is your basic implementation of Eratosthenes' Sieve. There are quite a few ways in which you can improve it, but let's go over the basic principle first.

What you are doing is creating an array of boolean values. The INDEX in the array represents the number which we are testing to see if it is a prime or not.

Now you are going to start checking each number to see if it is a prime. First off, the definition of a prime is "all numbers divisible ONLY by itself and 1 without fractioning".

for ( int i = 2; i < maxLimit; i++ )

You start with the INDEX 2 (the number 3) because depending on your definition, 1 and 2 are always prime. (Some definitions say 1 is not a prime).

if ( sieve[i] == true ) continue;

If a number has been marked as a non-prime previously, we don't bother with the current iteration.

numberOfPrimes++;

        if ( numberOfPrimes == 10001 ) {
            number = i; 
            break; 
        }

If the INDEX we are at currently has not been marked as being a prime, it has to be one, so we increment the number of primes we have found. The next piece of code I'm assuming is part of the requirements of the program which states that if 10001 primes have been found, the program must exit. That part can be left out if you actually want to check for primes up to the maximum number defined in stead of for a specific number of primes.

for ( int j = i+i; j < maxLimit; j += i )
            sieve[j] = true;

This is where the actual magic of the sieve starts. From the definition of a prime, a number cannot be a prime if it is divisible by anything other than itself and 1. Therefore, for any new number we find that is a prime, we can mark all it's factors as NOT being prime. For example, the first iteration of the for loop, we start with 3. Because sieve[2] is false (have not visited before), it is a prime (AND 3 IS A PRIME!). Then, all other factors of 3 CANNOT be primes. The above mentioned for loop goes through the entire sieve and marks all factors of 3 as false. So that loop will do: sieve[5] = true; sieve[8] = true ... up until the end of the sieve.

Now, when you reach the first number greater than the maximum defined initially, you can be certain that any number that has a factor has been marked as not being a prime. What you end up with is a boolean array, where each index marked as false, represents a prime number.

You can probably get a much better description on wikipedia, but this is the jist of it. Hope it helps!