Sieve of Eratosthenes

Question

For practice, I've implemented Sieve of Eratosthenes in Java by thinking about this visual animation.

I would like to hear some suggestions for improvements, especially how to make it more efficient and readable (sometimes there are trade offs) and how to follow good Java conventions. Also, suggestions on issues from naming conventions to proper javadoc are welcome as well. I'm just trying to improve my programming skills.

Incidently, the sieveOfEratosthenes method below is big O(?).

/**
 * returns a boolean array for prime numbers
 * @param max the maximum value to search for primes
 * @return boolean array of integers with primes true
 */
public boolean[] sieveOfEratosthenes(int max){

    boolean[] primeCandidates = new boolean[max]; //defaults to false
    for(int i=2; i<max; i++ ){primeCandidates[i]=true;}

    for(int i=2; i<Math.sqrt(max);i++){
        if(primeCandidates[i] == true){
            //all multiples of i*i, except i, are not primeCandidates
            for(int j = i + i; j<max; j=j+i){
                primeCandidates[j]=false;
            }
        }

    }
    return primeCandidates;
}

/**
 * print the index number for all true in given array
 * @param a boolean array
 */
public void printTrue(boolean[] arr){
    for(int i=0; i<arr.length; i++){
        if(arr[i]==true){
            System.out.print(i + ", ");
        }
    }
}

Answer 1

Input checking is missing. You should throw an IllegalArgumentException if max is less than zero instead of the NegativeArraySizeException.

Result of Math.sqrt(max) doesn't change, so maybe it's would worth to extract out to a local variable but maybe the JVM already optimize this for you.

Anyway, it's fine. I made some renaming and formatting, here is the result:

public boolean[] sieveOfEratosthenes(final int max) {
    if (max < 0) {
        throw new IllegalArgumentException("max cannot be less than zero: " + max);
    }
    final boolean[] primeCandidates = new boolean[max]; // defaults to false
    for (int i = 2; i < max; i++) {
        primeCandidates[i] = true;
    }

    final double maxRoot = Math.sqrt(max);
    for (int candidate = 2; candidate < maxRoot; candidate++) {
        if (primeCandidates[candidate]) {
            for (int j = 2 * candidate; j < max; j += candidate) {
                primeCandidates[j] = false;
            }
        }

    }
    return primeCandidates;
}

Answer 2

You asked about big O notation. I believe your implementation is O(n ln ln n).

(See this Stack Overflow discussion: "Why is Sieve of Eratosthenes more efficient than the simple “dumb” algorithm?")

By the way, instead of testing for:

i < Math.sqrt(max)

it is usually faster to test for:

i * i < max

Answer 3

To chip in an extra observation: boolean[] is memory-inefficient. In standard VMs it uses a byte per entry. For storing large arrays of Booleans, it's generally a good idea to prefer java.util.BitSet.

BitSet also has methods to clear and set large chunks of consecutive bits which work on a backing int[] and give a major speed-up – although that's probably not significant here, since you're unlikely to find that

for(int i=2; i<max; i++ ){primeCandidates[i]=true;}

is a bottleneck.

Answer 4

Because 2 is the only even prime number, you can eliminate about half of the loop iterations by incrementing i by 2 in the comparison loop instead of 1 (++). Set all non-2 even bits false initially, set the 2 bit to true, and use the initial set-to-true loop to set odd bits to true:

boolean[] primeCandidates = new boolean[max]; //defaults to false
primeCandidates[2]=true;
//2 is the only even prime number, so set only odd primeCandidates to true
for (int i = 3; i < max; i += 2) {
    primeCandidates[i] = true;
}
int limit = (int)Math.sqrt(max);
//because all non-2 primes are odd, skip checking even numbers
for (int i = 3; i < limit; i+=2){
    ...

Answer 5

There is is a mistake in the initial code that is changed in all the reply's but never mentioned.

for(int i=2; i<Math.sqrt(max);i++){
    if(primeCandidates[i] == true){
        //all multiples of i*i, except i, are not primeCandidates
        for(int j = i + i; j<max; j=j+i){
            primeCandidates[j]=false;
        }
    }

The inner for loop is incorrect you should be getting the square of i not the sum. It should read:

for(int j = i * i; j<max; j=j+i){

not:

for(int j = i + i; j<max; j=j+i){

Answer 6

• The following line

  for(int i=2; i<max; i++ ){primeCandidates[i]=true;}
  

  is very badly written without proper formatting. The correct way is to give space after ) and also both side of any operator such as =,+ for better readability.

  for(int i = 2; i < max; i++) {
      primeCandidates[i] = true;
  }
  

  However what are you trying to accomplish can be done in one line

  java.util.Arrays.fill(primeCandidates, true);
  

• Secondly since the default value for any boolean array is false I would take that advantage and change my code accordingly (borrowing palacsint's code)

  /**
   * Returns a boolean array with non-prime numbers as true.
   *
   */
  
  public boolean[] sieveOfEratosthenes(final int max) {
      if (max < 0) {
          throw new IllegalArgumentException("max cannot be less than zero: " + max);
      }
      final boolean[] compositeCandidates = new boolean[max];
  
      final double maxRoot = Math.sqrt(max);
      for (int candidate = 2; candidate < maxRoot; candidate++) {
          if (!compositeCandidates[candidate]) {
              for (int multiples = 2 * candidate; multiples < max; multiples += candidate) {
                  compositeCandidates[multiples] = true;
              }
          }
  
      }
      return compositeCandidates;
  }
  

Answer 7

On top of @Peter Taylor suggestion, you could use a LongBitSet implementation I worked on that addresses the limitations of BitSet. It will check invariants for you.

I address some details in this thread

The max value you could ask from it is around 137.4B: 137,438,953,215. It'd need 24GB heap size.

Code improvements (readability):

There area few improvements:

• Capacity (long vs int).
• Performance over BitSet.
• Using LongBitSet::set(long, long) interface for setting ranges.
• Eliminate boolean == true conditional
• Invariants checked in LongBitSet. (index out fo bounds and such.)

    public static LongBitSet sieveOfEratosthenes(long max){

        primeCandidates = new LongBitSet(max); //defaults to false
        primeCandidates.set(2L, max);

        for(long i=2; i<Math.sqrt(max);i++){
            if(primeCandidates.get(i)) {
                // all multiples of i*i, except i, are not primeCandidates
                for(long j = i + i; j<max; j=j+i)
                    primeCandidates.clear(j);
            }
        }
        return primeCandidates;
    }

**Though not very performant

For a LongBitSet of 6,469,693,230 bits (about 3.01 times Integer.MAX_VALUE):
 * sieveOfEratosthenes Finished in 197851.923439 milliseconds. //197secs
 * My Sieve Finished in 39176.820695 milliseconds. //39secs

If performance is not important (IMO for sieves it is...), avoiding nesting and using streams makes it more linear (instead of back and forth) to read.

    public static LongBitSet neatSieveOfEratosthenes(long max){
        primeCandidates = new LongBitSet(max);
        primeCandidates.set(2L, max);

        final long maxSqrt = (long) Math.sqrt(max);
        LongStream.iterate(2, l -> l++)
                .limit(maxSqrt)
                .filter(primeCandidates::get)
                .forEach(l -> clearMultiples(l, maxSqrt));
        return primeCandidates;
    }

    private static void clearMultiples(long i, long max) {
        for(long j = i + i; j < max; j=j+i)
            primeCandidates.clear(j);
    }

Answer 8

Since there are fewer primes, you could use a list of some kind to hold the prime numbers.

For every prime number n greater than 3,

n mod 6 = 1 or n mod 6 = 5.

If you could somehow not check other numbers for prime, you might save on some primeness checking.