# Implementation of Sieve of Eratosthenes algorithm

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?

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.

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;
}


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;


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.

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.