6
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ FYI, class names in Java start with a capital letter as per convention, so the class should be named SieveOfEratosthenes. \$\endgroup\$ – Ingo Bürk Aug 19 '15 at 4:57
5
\$\begingroup\$
  • 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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you, I have worked to improve the organisation of my code (you can see the new code here: dropbox.com/s/wvruqag29lyhwej/sieveOfEratosthenes.java?dl=0) although, I am not sure what you mean about taking advantage of maxNumToTest as placing it in other loops will cause it to print the wrong output? \$\endgroup\$ – James Aug 18 '15 at 13:57
  • \$\begingroup\$ I have updated my answer but be aware I didn't test this. \$\endgroup\$ – Heslacher Aug 18 '15 at 14:02
  • \$\begingroup\$ I see what you have tried, although I have tried implementing this in my code and it does not give the correct output! If we look at an example, if we inputted 10, the maxNumToTest would be 3, so if, in our inner loop we only tested upto maxNumToTest, we would never have tested 4, 5, 6, ..., 10. Likewise, in the output loop, some of the numbers above 3 are also prime, and would not be printed! \$\endgroup\$ – James Aug 18 '15 at 14:06
  • 1
    \$\begingroup\$ striked through \$\endgroup\$ – Heslacher Aug 18 '15 at 14:08
5
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I agree with your first comment about skipping even numbers, although, in terms of the trade off between memory useage and efficency, would the impact overall on time taken outweight the benifits of using less memory? \$\endgroup\$ – James Aug 18 '15 at 19:56
  • \$\begingroup\$ @JamesZafar I updated my answer to give an example using 1 bit per odd number. You should try it out and see if it is faster on your machine. \$\endgroup\$ – JS1 Aug 18 '15 at 20:46
  • \$\begingroup\$ You should use BitSet for this. Then you don't have to calculate everything and the code could be cleaner. \$\endgroup\$ – Obenland Aug 19 '15 at 17:57
  • \$\begingroup\$ @Xean I tried a BitSet just now but it was 3x slower than using the array of int. \$\endgroup\$ – JS1 Aug 19 '15 at 18:09
  • \$\begingroup\$ @JS1 this is strange. A BitSet is doing the same with an array of long. No much extra stuff. Did you use the right constructor to set the length, so it doesn't have to expand? \$\endgroup\$ – Obenland Aug 19 '15 at 18:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.