• 1

• 507
• 1
• 5
• 11

• 507
• 1
• 5
• 11

I previously asked about my implementation of the Sieve of Eratosthenes algorithm [here][1].

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.

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? [1]: Implementation of Sieve of Eratosthenes algorithm