Implementation of Sieve of Eratosthenes algorithm

Question

I have made an implementation of Sieve of Eratosthenes algorithm in Java, and am not certain that it is as efficient as possible.

I have looked at other peoples implementations on Google, and on this site, which raised concerns for me, as no one has taken a similar approach to me.

public class sieveOfEratosthenes {
    public static void main (String [] args) {
        int maxPrime;
        try (java.util.Scanner tempInput = new java.util.Scanner(System.in)) {
            System.out.println("What number would you like the prime numbers to be generated to?");
            maxPrime = tempInput.nextInt();
            tempInput.close();
        }
        System.out.println("Computing list...");
        long start = System.nanoTime();
        int [] numberList = new int [(maxPrime - 1)];
        boolean [] isPrime = new boolean [(maxPrime - 1)];
        for(int i = 0; i < (maxPrime - 1); i++) {
            numberList[i] = (i + 2);
            isPrime[i] = true;
        }
        int maxTestNum = (int) Math.sqrt(maxPrime);
        int tempAns;
        for(int j = 0; j < maxTestNum; j++) {
            int temp = numberList[j];
            if(isPrime[j] == true) {
                temp = numberList[j];
            }
            for(int k = j; k < (numberList.length - 1); k++) {
                for(int p = 2; p <= numberList.length; p++) {
                    tempAns = temp * p;
                    if(tempAns > maxPrime) {
                        break;
                    }
                    for(int z = 0; z < numberList.length; z++) {
                        if(numberList[z] == tempAns) {
                            isPrime[z] = false;
                        }
                    }
                }
            }
        }
        long stop = System.nanoTime();
        System.out.print("Prime numbers than are <= " + maxPrime + ": ");
        for(int n = 0; n < numberList.length; n++) {
            if (isPrime[n] == true) {
                System.out.print(numberList[n] + " ");
            }
        }
        System.out.println();
        System.out.println("Execution time: " + ((stop - start) / 1e+6) + "ms");
    }
}

The issues I came across whilst creating it were:

• What is the best way of storing a list of numbers?

• Is there a more efficient way of generating a list of numbers, rather than just using a for loop?

• How efficient are arrays? Is there a more efficent 'version' of an array that could have been used to store/access data?

Answer 1

What is the best way of storing a list of numbers?

Not doing them at all? It's both the fastest and the most memory-efficient solution.

And it applies perfectly to your use case as numberList[i] == i+2 always holds.

Is there a more efficent way of generating a list of numbers, rather than just using a for loop.

There are many ways to speed it up, but there's actually always such a loop. One trivial optimization is to ignore even numbers.

How efficent are arrays?

It's the fastest storage when you access data either sequentially or by index. So concerning isPrime, it's the best what you can do (unless you want to trade speed for memory, then look at BitSet).

Concerning numberList, it'd be much better to drop it. Computing i+2 is surely way faster than reading numberList[i].

---

Now I have a question: How can you code be used? The answer is that

• not without user interaction
• not without reading the console
• not for task like this one

How can it be improved: Separation of concerns. Luckily it's very easy to do in your case: Just extract methods (the IDE can do it for you):

• readInput
• sieve
• printResult

Review

    int maxPrime;

Note that it's (usually) no prime at all.

    int [] numberList = new int [(maxPrime - 1)];
    boolean [] isPrime = new boolean [(maxPrime - 1)];
    for(int i = 0; i < (maxPrime - 1); i++) {
        numberList[i] = (i + 2);
        isPrime[i] = true;
    }

Drop numberList, use Arrays.fill(isPrime, true).

    int tempAns;

You don't need it here.

        int temp = numberList[j];
        if(isPrime[j] == true) {
            temp = numberList[j];
        }

You mean, "in case of a prime, we really want that temp has the value already assigned and assign it once more, just in case".

        for(int k = j; k < (numberList.length - 1); k++) {

No need for parentheses here.

                for(int z = 0; z < numberList.length; z++) {
                    if(numberList[z] == tempAns) {
                        isPrime[z] = false;
                    }
                }

This makes your code very slow. You could do (possibly after some bounds checks)

 isPrime[tempAns-2] == false;

and save yourself a loop.

But actually you should simplify it so that you do just

 isPrime[tempAns] == false;

s saving two elements of a potentially huge array makes no sense. Btw., tempAns is a really bad name (even worse thantemp). Call it product.

        if (isPrime[n] == true) {

Don't do it. All the following expressions are equivalent:

• isPrime[n]
• isPrime[n] == true
• (isPrime[n] == true) == true
• ((isPrime[n] == true) == true) == true
• (((isPrime[n] == true) == true) == true) == true

Just use the simplest one.

Answer 2

Usually there is no need for an explicit Array of numbers.

The index you use to accesss the elements in the isPrime is the number you are testing.

To make it explicit instead of

if(isPrime[j] == true) {
     temp = numberList[j];
}

if you don't use the additional numberList you could rewrite it as

if(isPrime[j] == true) {
     temp = j;
}

Which saves you an access to the element array via index.

This would allow you also to write

for(int z = 0; z < numberList.length; z++) {
   if(numberList[z] == tempAns) {
      isPrime[z] = false;
   }
}

as

isPrime[tempAns] = false; 

Some additional remarks about your code:

int maxTestNum = (int) Math.sqrt(maxPrime);

should be

int maxTestNum = (int) Math.ceil(Math.sqrt(maxPrime));

which saves you at least for each outer loop steps 2 * numberList.length accesses to the arrays via index (i.e. numberList[z] and isPrime[z])

int temp = numberList[j];
if(isPrime[j] == true) {
     temp = numberList[j];
}

seems to be wrong. You unconditionally assign temp the value of numberList[j] and afterwards you check for isPrime[j] == true and repeat that assignment.

Disadvantange of the suggested approach is that the isPrime array contains two additonal elements for the numbers 0 and 1. For the execution time this is usually is negligible - especially for big maxPrimes.

For your Questions

• The best way of "storing" the numbers is not to store them explicitly.

• No there is no more efficient way than the loop to fill an array with numbers - except to avoid it.

• Accessing the a primitive array via index is constant in time - no there is no more efficient data structure for this kind of access.

Answer 3

int [] numberList is probably redundant. AFAIK a standard implementation of the sieve needs only a boolean-array, as it is enough to store the information if a number is prime.

You have quite many (four) nested for-loops (3 with numberList.length, one with Math.sqrt(max)), this is most probably too complicated/slow/not needed. A simple implementation (which are also on this site, for example Sieve of Eratosthenes) only needs two nested loops.

The complexity of your algorithm is probably not optimal. On a modern computer, a simple implementation of the sieve should be able to calculate the number of primes below 1 million or 10 million almost instantly. How long does it take for you?