12
\$\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\$
11
\$\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\$
  • 4
    \$\begingroup\$ I'd additionally rename the first i to idx, remove the == true check and rename j. \$\endgroup\$ – Bobby Jan 10 '12 at 12:00
6
\$\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\$
  • 1
    \$\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 '15 at 13:12
5
\$\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\$
  • 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 '14 at 20:17
  • \$\begingroup\$ @Geobits, interesting. I didn't profile, but I would have expected that the JIT would take care of that. \$\endgroup\$ – Peter Taylor Feb 13 '14 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 '14 at 0:21
3
\$\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\$
2
\$\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\$
  • \$\begingroup\$ Well, it's an efficiency problem, not a bug in terms of correctness. \$\endgroup\$ – 200_success May 13 '15 at 23:01
1
\$\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\$
  • \$\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 '14 at 20:05
-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\$

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.