I previously asked about my implementation of the Sieve of Eratosthenes algorithm here.
After looking at all of the feedback, I have reworked the code to make it significantly more efficient. However, I'd like to know whether it can be made more efficient still.
I have tried to follow pesudocode for my implementation, which I have provided below:
Input: an integer n > 1
Let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.
for i = 2, 3, 4, ..., not exceeding √n:
if A[i] is true:
for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n :
A[j] := false
Output: all i such that A[i] is true.
Pseudocode sourced from here.
My implementation:
import java.util.Arrays;
import java.util.Scanner;
public class sieveOfEratosthenes {
public static void main (String [] args) {
int maxPrime;
try (Scanner sc = new Scanner(System.in);) {
System.out.print("Enter an integer greater than 1: ");
maxPrime = sc.nextInt();
sc.close();
}
long start = System.nanoTime();
boolean [] primeNumbers = new boolean [maxPrime];
Arrays.fill(primeNumbers, true);
int maxNumToTest = (int) (Math.floor(Math.sqrt(maxPrime)));
for(int i = 2; i <= maxNumToTest; i++) {
if (primeNumbers[i] == true) {
for (int j = i * i; j < maxPrime; j += i) {
primeNumbers[j] = false;
}
}
}
long stop = System.nanoTime();
for(int i = 2; i < primeNumbers.length; i++) {
if(primeNumbers[i] == true) {
System.out.print((i) + ", ");
}
}
System.out.println("\nExecution time: " + ((stop - start) / 1e+6) + "ms.");
}
}
I have tested my implementation to find that it is capable of calculating all primes below 10,000,000 in ~110ms on an i5 processor.
My question: Is this as fast as is physically possible in Java, or can I make further improvements?
SieveOfEratosthenes
. \$\endgroup\$ – Ingo Bürk Aug 19 '15 at 4:57