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?