Java Implementation of Sieve of Eratosthenes algorithm

Question

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?

Answer 1

• 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 <= maxNumToTest; i++) {
        if (primeNumbers[i]) {
            for (int j = i * i; j <= maxNumToTest; j += i) {
                primeNumbers[j] = false;
            }        
        }
    }
    long stop = System.nanoTime();
    for(int i = 2; i <= 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.

Answer 2

Skip even numbers

If you do 2 as a special case, you can skip all even numbers later on. This helps in 2 places:

1. You can only check odd numbers for primes.
2. After you find a prime number and you are doing the sieve, you can increment by 2*i instead of just i.

Here is what your code would look like:

    int maxNumToTest = (int) (Math.floor(Math.sqrt(maxPrime)));
    // Special case for prime number 2:
    for(int i = 4; i < maxPrime; i += 2) {
        primeNumbers[i] = false;
    }
    // Now the normal case can skip all even numbers.
    for(int i = 3; i <= maxNumToTest; i += 2) {
        if (primeNumbers[i] == true) {
            int increment = i+i;
            for (int j = i * i; j < maxPrime; j += increment) {
                primeNumbers[j] = false;
            }
        }
    }

I tested this change and it was faster than the original code by 20-25%.

Memory usage

I extended your program to search for larger and larger prime numbers but at a certain point I ran out of memory. Currently, your program is using 1 byte per number. One thing you could do to use less memory would be to allocate half the number of booleans (only for the odd numbers). For even lower memory usage, you could use 1 bit per odd number. These changes would reduce your memory usage by 16x, and could potentially speed things up.

Here is an example of using 1 bit per odd number:

    // Each bit is an odd number.  Bit 0 = 1, bit 1 = 3, bit 2 = 5, etc.
    int [] primeNumbers = new int[(maxPrime+63)/64 + 1];
    Arrays.fill(primeNumbers, 0xffffffff);
    // Clear the bit for any number >= maxPrime:
    int lastNumber = primeNumbers.length * 64 - 1;
    for (int i = maxPrime; i < lastNumber; i++) {
        int iIndex = i >> 6;
        int iBit   = (1 << ((i >> 1) & 31));
        primeNumbers[iIndex] &= ~iBit;
    }
    // 1 is not a prime.
    primeNumbers[0] &= ~0x1;
    int maxNumToTest = (int) (Math.floor(Math.sqrt(maxPrime)));
    for(int i = 3; i <= maxNumToTest; i += 2) {
        int iIndex = i >> 6;
        int iBit   = (1 << ((i >> 1) & 31));
        if ((primeNumbers[iIndex] & iBit) != 0) {
            int increment = i+i;
            for (int j = i * i; j < maxPrime; j += increment) {
                int jIndex = j >> 6;
                int jBit   = (1 << ((j >> 1) & 31));
                primeNumbers[jIndex] &= ~jBit;
            }
        }
    }
    long stop = System.nanoTime();
    System.out.print("2, ");
    for(int i = 3; i < maxPrime; i+=2) {
        int iIndex = i >> 6;
        int iBit   = (1 << ((i >> 1) & 31));
        if((primeNumbers[iIndex] & iBit) != 0) {
            System.out.print((i) + ", ");
        }
    }

On my machine, this appears to run faster than using an array of booleans. But you should test it yourself because the size of your cache matters a lot when doing this.