13
\$\begingroup\$

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 + ", ");
        }
    }
}
\$\endgroup\$

8 Answers 8

12
\$\begingroup\$

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;
}
\$\endgroup\$
1
  • 4
    \$\begingroup\$ I'd additionally rename the first i to idx, remove the == true check and rename j. \$\endgroup\$
    – Bobby
    Jan 10, 2012 at 12:00
7
\$\begingroup\$

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
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Actually i*i < max is slower than i < Math.sqrt(max) in practice because the JIT can deduce that Math.sqrt(max) is constant and move it out of the iteration (easy). It's harder for the compiler to remove the multiplication in your example. At any rate the fastest code to regardless of optimization is just: int sqrt_max = (int)Math.sqrt(max); for(...; i < sqrt_max; ...). Your example is useful when you're not repeatedly looping and testing the condition. For example seeing which of two vectors is longer. \$\endgroup\$
    – Emily L.
    Jul 2, 2015 at 13:12
  • \$\begingroup\$ @EmilyL. — Excellent point, thanks. :) \$\endgroup\$ Dec 20, 2021 at 18:42
7
\$\begingroup\$

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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ BitSet is a great way to save memory, but it definitely slows it down. Any speed improvement gained from the ability to set/clear chunks is outweighed by making the get() call every time you look at an entry. In my sieve, using BitSet took about 40% longer for large sieves. \$\endgroup\$
    – Geobits
    Feb 13, 2014 at 20:17
  • \$\begingroup\$ @Geobits, interesting. I didn't profile, but I would have expected that the JIT would take care of that. \$\endgroup\$ Feb 13, 2014 at 23:21
  • \$\begingroup\$ @Geobits, yes, that's interesting. Do you have any timing values that I could compare with? I wrote an implementation of this algorithm using a BitSet and it will find all of the primes up to the maximum integer - 2 in about 40 seconds. I thought this was pretty good, but maybe I was just being naive? \$\endgroup\$
    – Mark Ross
    Jul 7, 2014 at 0:21
5
\$\begingroup\$

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){
    ...
\$\endgroup\$
4
\$\begingroup\$

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){
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Well, it's an efficiency problem, not a bug in terms of correctness. \$\endgroup\$ May 13, 2015 at 23:01
2
\$\begingroup\$
  • 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;
    }
    
\$\endgroup\$
1
  • \$\begingroup\$ There is no "correct" code style, it's a matter of convention (and I personally find a different style mor readable). The thing one wants to look out for is consistency. \$\endgroup\$
    – Ingo Bürk
    Apr 28, 2014 at 20:05
2
\$\begingroup\$

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);
    }
\$\endgroup\$
4
  • \$\begingroup\$ How would this improve the original code, which is the point of code review? \$\endgroup\$
    – pacmaninbw
    Dec 20, 2021 at 14:32
  • \$\begingroup\$ There area few improvements: capacity (long vs int) performance over BitSet. Using BitSet interface for setting ranges. Eliminate boolean == true conditional. \$\endgroup\$
    – juanmf
    Dec 20, 2021 at 15:09
  • 1
    \$\begingroup\$ Can you state in the answer how it improves the code. \$\endgroup\$
    – pacmaninbw
    Dec 20, 2021 at 15:11
  • \$\begingroup\$ Also added a stream based approach that makes it linear to read. Thanks for the callout. \$\endgroup\$
    – juanmf
    Dec 20, 2021 at 17:31
-1
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Primes are around x/log(x) as many as natural numbers (x), . Think a BitSet is much more convenient in the end, unless very far from zero (Billions) which this program doesn't reach. \$\endgroup\$
    – juanmf
    Dec 20, 2021 at 18:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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