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) {
                        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.

StackExchange Code Review Q#95542, answer score: 2