Optimize Speed of Prime Number Sieve (Java)

Question

I'm working on a method in Java which creates boolean array isPrime:

boolean[] isPrime;

in which prime numbers are labeled with 'true' and the rest with 'false'.
While I'm at it I'd also like to count the number of Primes found:

int numPrimesFound;

The basic idea is to use the Sieve of Eratosthenes. So far my method looks like this:

public Sieve(final int limit) {

    long startTime = System.currentTimeMillis();

    boolean[] isPrime = new boolean[limit];
    this.isPrime = isPrime;

    for (int i=3; i<=limit ;i+=2) {
        isPrime[i] = true;                        //sets all even numbers to true
    }

    isPrime[2] = true;
    numPrimesFound = 1;                           //special case of '2'

    for (int i = 3; i * i <= limit; i += 2) {
        if (isPrime[i] == true) {
            for (int j = i; i * j <= limit; j += 2) {

                isPrime[i * j] = false;           //has a multiple ==> not a prime

                numPrimesFound++;                 //doesn't work yet
            }
        }
    }

    long stopTime = System.currentTimeMillis();   //measuring execution time
    System.out.println("Sieve: " + (stopTime - startTime) + " milliseconds.")

}

So my problem is that

numPrimesFound++:

doesn't work because the sieve sets the value of some non-prime numbers to 'false' more than once (e.g. 45 bcs 3*15 = 45 and 9*5 = 45).
So does anybody have a clue on how I could rewrite this program so it sets all the non-prime numbers to 'false' only once?

Or generally speaking, can anybody suggest ways to make the method faster?

Which result are you interested in: the count of primes, or the primes themselves? As you've seen, `numPrimesFound` is wrong, but that's unrelated to the speed of the algorithm finding primes. Also: you should probably read [How to write a correct microbenchmark in Java](http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java). — Daniel Pryden, Dec 24 '15 at 16:49
get rid of the multiplications in the inner loop, leave only additions there: `i*(j + 2) == i*j + 2*i`. — Will Ness, Jan 02 '16 at 00:39

OldCurmudgeon · Answer 1 · 2015-12-24T17:17:32.413

If you use a BitSet you can ask for it's cardinality.

public BitSet primes(final int limit) {

    long startTime = System.currentTimeMillis();
    BitSet isPrime = new BitSet(limit);
    // A bitSet starts all zeros but with a sieve - evrything must start prime.
    isPrime.flip(0, limit);

    // 0 and 1 are not prime
    isPrime.clear(0);
    isPrime.clear(1);

    for (int i = 2; i * i <= limit; i += 2) {
        if (isPrime.get(i)) {
            // Remove all multiples of i.
            for (int j = 2; i * j <= limit; j += 1) {
                isPrime.clear(i * j);
            }
        }
    }

    long stopTime = System.currentTimeMillis();   //measuring execution time
    System.out.println("Sieve: " + (stopTime - startTime) + " milliseconds.");
    return isPrime;
}

public void test() {
    BitSet primes = primes(50);
    System.out.println("Primes: " + primes);
    System.out.println("Count: " + primes.cardinality());
}

I've also fixed a couple of errors in your logic. E.g. your inner loop was stepping j by 2 and your outer loop was not removing all even numbers (started at 3).

You can certainly improve on this - google is your friend. :)

To avoid initial flipping, use set instead of clear and then return limit - cardinality — Kostas Kryptos, Dec 24 '15 at 18:14

Hoang Tran duy · Answer 2 · 2020-12-10T00:20:45.703

Here is my version (it calculates only the set that contains possible prime factors of the input number):

import java.util.BitSet;
import java.util.Scanner;

public class Main {

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter the interval limit: ");
    int limit = sc.nextInt();
    int max = (int) Math.sqrt(limit);
    long start = System.currentTimeMillis();
    BitSet intArray = new BitSet(max);

    // 1 is not prime
    intArray.set(0);

    // 2 is the first prime number, so the first step is to filter out all even numbers
    for (int i = 2; i < limit; i+=2) {
        intArray.set(i);
    }

    //all remaining number will be odd
    int currentNumber = 3;
    // i is the multiplicator and will be adjusted with the current number , in order to avoid repetition
    int i = 3;
    int temp;

    while (currentNumber <= max) {
        // flag multiple of the current prime number
        while (true) {
            temp = (currentNumber * i);
            if (temp > max) break;
            intArray.set(temp - 1);
            i += 2;
        }
        //all non-prime numbers until now are already flagged, therefore we can find the next prime number by checking the set-status.
        while (true) {
            currentNumber += 2;
            if (currentNumber > max) break;
            if (!intArray.get(currentNumber - 1)) {
                i = currentNumber;
                break;
            }
        }
    }

    int b = 0;
    for (int n = max -1 ; n > 0; n--){
        if (!intArray.get(n)){
            b = n + 1;
            break;
        }
    }
    System.out.println("There are " + (max - intArray.cardinality()) + " PRIMES and the biggest is: " + b);
    System.out.println("Time in total: " + ((System.currentTimeMillis() - start) / 1000.0) + "s");
}
}

To check 100 mio numbers, it needs ca. 0,7 s on my i7 3770k desktop pc.

you might want to drop some lines as to what does the code do — amonk, Jan 25 '18 at 13:08
Just added few comments. I hope that it is easier now to unterstand. — Hoang Tran duy, Jan 25 '18 at 13:25

guillaume girod-vitouchkina · Answer 3 · 2015-12-24T17:03:05.557

You have a confusion:

numPrimesFound++; is ok but it must be outside the loop for (int j = i; i * j <= limit; j += 2)

your principal loop must go farther (or you forget primes bigger than sqrt(limit)

 for (int i = 3; i < limit; i += 2)

it is normal in Eratosthenes Sieve, to mark several times "non-prime" numbers.

and i * j < limit is NOK if it become bigger than int (it becomes negative)

Result is OK like that, but only with

final int limit=40000; // 50 000 is too big !

replace you inner loop with that, and you can go to 1000000 at least

 for (int z = i*2; z<limit; z+=i)
    isPrime[z] = false;           //has a multiple ==> not a prime

And you could use bitset

score 0 · Answer 4 · answered Dec 24 '15 at 17:55

ok.. Here is what I came up with

long startTime = System.currentTimeMillis();
int limit = 100000;
boolean[] isPrime = new boolean[limit+1];

Arrays.fill(isPrime, true);
isPrime[0] = false;
isPrime[1] = false;
int numPrimesFound = limit-1;                           

System.out.println("Sqrt is:" + Math.sqrt(limit));
for (int i=2; i < Math.sqrt(limit);i++) {
    if (isPrime[i] == true) {
        int inc = 0;
        while (true) {
            int j = (i*i) + (inc*i);
            if( j > limit) break;
            if (isPrime[j]) {
                isPrime[j]= false;
                numPrimesFound--;     
            }
            inc++;
        }
    }
}

System.out.println("Number of Primes" + numPrimesFound);
for (int i = 2; i < limit;i++) {
    if (isPrime[i]) 
        System.out.println("Prime#:" + i);
}
long stopTime = System.currentTimeMillis();   //measuring execution time
System.out.println("Sieve: " + (stopTime - startTime) + " milliseconds.");

Optimize Speed of Prime Number Sieve (Java)

4 Answers4