Java Implementation of Sieve of Eratosthenes algorithm 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 &gt; 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 &lt;= maxNumToTest; i++) {
            if (primeNumbers[i] == true) {
                for (int j = i * i; j &lt; maxPrime; j += i) {
                    primeNumbers[j] = false;
                }        
            }
        }
        long stop = System.nanoTime();
        for(int i = 2; i &lt; 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?
Using vertical spaces (new line) to group related code will help to easier read your code.  
if(primeNumbers[i] == true) the checking with == true is superfluous because the condition of the if is a boolean one, so you can simplify this to if(primeNumbers[i])  



- instead of using maxPrime here  

    boolean [] primeNumbers = new boolean [maxPrime];
    Arrays.fill(primeNumbers, true) 


you should take advantage of the computed int maxNumToTest like you did in the first loop. You should also add this computed value as the end of the inner loop and the result loop like so    

    int maxNumToTest = (int) (Math.floor(Math.sqrt(maxPrime)));        
    boolean [] primeNumbers = new boolean [maxNumToTest];
    Arrays.fill(primeNumbers, true);

    for(int i = 2; i &lt;= maxNumToTest; i++) {
        if (primeNumbers[i]) {
            for (int j = i * i; j &lt;= maxNumToTest; j += i) {
                primeNumbers[j] = false;
            }        
        }
    }
    long stop = System.nanoTime();
    for(int i = 2; i &lt;= maxNumToTest; i++) {
        if(primeNumbers[i]) {
            System.out.print((i) + ", ");
        }
    }



- putting everything int main() should be avoided. The current code could be divided into 3 methods:  


reading the input
computing the primes
writing the output  

In this way each method has a single responsibility and is easier to read and to maintain.