Space and time efficient Algorithm for generating prime numbers

Question

I have developed an algorithm for generating prime numbers (which turns out to be an optimized version of the Sieve of Eratosthenes) by reducing the space by a factor of 64.

/*
 * Explanation of algorithm

 * 1. Avoid storing all the even numbers as they cnt b prime numbers - so divide the size by 2

 * 2. Represent each bit of int as a odd number 1,3,5,7 and so on. Each int has 32 bits and will store prime numbers between 0 to 63.

 * 3. Again divide the counter by 32, so now the final size of the array would be 32*2=64 (because we are also avoiding even numbers)

 * 4. 1st Loop (i)-  Loop from i=3 upto squareroot of the given range and increment by 2(because we don't care about the even numbers)

 * 5. 2nd Loop (j)- Loop from square of the current number(i) till its less than the counter and increment j by 2*i (Again avoid the even number multiples)

 * 6. Mark all the multiples of the j to 1/true.(In our code we set the corresponding bit to 1) 
 for e:g for setting 9 to be non-prime we simply divide it by 2 and set that bit to 1.

 * 7. While printing we check if the bit is set to 0. if yes, then print the number by multiplying (32*[currentIndexInArray]+bit-position)*2 +1.



 * Note: it will correctly print all numbers from 3 to given range(should be multiples of 64) 

 *  Even if its not multiple of 64, it still works but wont consider the last 32 numbers in the range.

 *  Also, it prints 1 in the output and not 2, which probably can be handle by extra conditions.
 *  its more focused on generating primes above number 3.
 */

public class PrimeNumberOptimized {
    static int range = 256;

    public static void main(String[] args) {

        long startTime = System.currentTimeMillis();

        int[] NonPrimeNumbers = new int[(range>>6)+1];

        int k=0;
        for(int i=3;i*i <= range;i+=2){
            //Increment k, everytime i goes beyond int size 
            if((i>>1)%32==0)
                k++;

            //Check if it is a prime number, if yes, mark all the bits which are multiples of this number.
            if((NonPrimeNumbers[k]&(1<<(i>>1)))==0)
            {
                for(int j=i*i;j <= range;j+=2*i){// increment j by 2*i, for :eg if i=5, then mark directly 15 skipping 10 as every alternate multiple will be an even number
                    //set the bit to 1. if i=3 and j=9, then we go to the 1st index in array and set the 9/2th bit in array value.
                    NonPrimeNumbers[j>>6]|=1<<(j>>1);
                }
            }
        }

        int primeCnt = 0;
        range >>= 6; // Divide the range by 64 as we need to iterate through the array which is reduced by factor of 64.

        for(int arrayIndex=0;arrayIndex < range;arrayIndex++){
            for(int bitPosition=0;bitPosition<32;bitPosition++) // Go through each bit of the array value
            {
                if((NonPrimeNumbers[arrayIndex]&(1<<bitPosition))==0) // check if the current bit is set to 0, if yes, then it represent prime number.
                {
                    System.out.println(((32*arrayIndex+bitPosition)*2)+1); // multiply by 32 to get the correct index in array, add the bitPosition to it and multiply by 2(again we are avoiding even numbers)
                    primeCnt++;
                }
            }
        }

        System.out.println("-Total no of Primes generated->"+(primeCnt));
        System.out.println("Total time ="+(System.currentTimeMillis()-startTime));
    }

}

Please have a look into this and let me know if it can be optimized any further. Compared with most of the algorithms found online and so far it's quite fast compare to other algorithms.

Answer 1

Coding style

First, let me comment on your coding style / readability:

NonPrimeNumbers does not follow Java Naming Conventions. Local variables should start with lower case.

Your variable names are simply bad.

• i is the candidate prime number, so its name should reflect that, e.g. candidatePrime.
• k should become arrayIndex (as you did when printing the results).
• j should become multiple.
• When finding the primes, you should also use the variable name bitPosition instead of (i>>1)%32.

Don't reuse variables for two different meanings, as you did with range. Use two different ones, e.g. primesRange and arrayRange.

At mostly all places where you added comments, introduce method calls instead of one big ugly main() method.

• (NonPrimeNumbers[k]&(1<<(i>>1)))==0 then should read isPrime(candidatePrime) or isPrime(arrayIndex,bitPosition).
• NonPrimeNumbers[j>>6]|=1<<(j>>1) should become setNonPrime(multiple).
• and so on.

Of course, NonPrimeNumbers then has to become an instance field instead of a local var.

Performance

You seem to be looking for performance. I won't do a detailed profiling of your program, that task is up to you. But you can check some modifications that might speed up your program (esp. for bigger prime numbers):

Instead of the single for(int i=3;i*i <= range;i+=2) loop you could try two nested loops, with an intermediate check if a prime number is possible:

for (int arrayIndex=0; arrayIndex<arrayRange; arrayIndex++) {
    if (nonPrimeNumbers[arrayIndex] != 0xffffffff) {
        for (int bitPosition = 0, pattern = 1; 
             bitPosition < 32; 
             bitPosition++, pattern <<= 1) {
            ...
        }
    }
}

Maybe you can mostly do without the candidatePrime variable, just with arrayIndex and bitPosition, only using it when you found a prime.

You have to try what gives you the best performance...

Answer 2

Space efficiency:

Currently you are storing 50% of all values, this can be reduced to 33% quite easily by not storing any multiples of 3. (Excluding additional values is possible but complicates the calculation between value and index, you might have to check until which point excluding values is advantaguous.)

Sidenote: You reduced the space consumption by the factor 2*8=16, not 64, compared to an implementation that uses a boolean[] (at least for the OracleJVM).

Performance:

You are iterating over each bit, I would use Integer#numberOfTrailingZeros to process the bits in blocks of 32 bits.
You might want to use multiple threads to sieve, a simple implementation could use multiple threads to strike of multiples of different starting values.
^{_{(For comparison: my quite similar implementation that skips multiples of 3 (and uses long[] instead of int[]) is around 25% (singlethreaded)/60% (multithreaded) faster than your current implementation.)}}

Implementation:

You don't need the variable k as it is equivalent to i>>6.
Your current implementation may overflow for larger sieve sizes.
I would iterate over the indices rather than over the values to avoid converting value->index while striking values off.

Possible implementation (the resulting array should be encapsulated in a Sieve class that provides methods to operate on the sieved values):

private static int[] sieve(int range) {
    int[] arr = new int[toIndex(range) + 31 >> 5];
    int n = arr.length << 5;
    for (int i = 0, j; (j = 2 * i * (i + 3) + 3) < n; i = nextClearBit(arr, i + 1)) {
        do {
            setBit(arr, j);
        } while ((j += 2 * i + 3) < n);
    }
    return arr;
}

private static int nextClearBit(int[] bits, int i) {
    final int len = bits.length;
    for (int c = (1 << i) - 1 | bits[i >>= 5];; c = bits[i]) {
        if (  c !=  -1) return (i << 5) + numberOfTrailingZeros(~c);
        if (++i == len) return len << 5;
    }
}

private static void setBit(int[] bits, int i) {
    bits[i >> 5] |= 1 << i;
}

private static int toIndex(int val) {
    return val - 3 >> 1;
}

private static int toValue(int pos) {
    return (pos << 1) + 3;
}