Sieve of Eratosthenes in Java

Question

Here you can find my implementation of sieve of Eratosthenes in Java.

/**
 * Return an array of prime numbers up to upperLimit
 * using sieve of Erastosthenes.
 * @param upperLimit
 * @return array of prime numbers up to upperLimit
 */
public static int[] sieve(int upperLimit) {
    // for corner cases
    if (upperLimit < 2) {
        return new int[0];
    }

    if (upperLimit == 2) {
        int[] result = {2};
        return result;
    }
    //--

    int arrLength = ((upperLimit - 3) / 2) + 1;

    // This arrray will be used to perform the sieve
    int[] temp = new int[arrLength];

    // Counter for number of primes encountered
    int numPrimes = 1; // because of 2

    // populate temp array with with 3,5,7,...,upperLimit
    for(int i=3; i <= upperLimit; i=i+2) {
        temp[(i-3) / 2] = i;
    }

    // Perform sieve
    for(int i=0; i < arrLength; i++ ) {
        int num = temp[i];
        if (num == 0) continue;
        numPrimes++;
        for (int k = i+num; k < arrLength; k=k+num) {
            temp[k] = 0;
        }
    }

    // Create result array
    int[] result = new int[numPrimes];
    result[0] = 2;
    int currentIndex = 1;

    for(int i: temp) {
        if (i!=0) result[currentIndex++] = i;
    }

    return result;
}

How does it look?

Answer 1

A few notes:

Right now you are using int[]s to represent the sieve. However, the int data type is internally stored as 32-bits, which is a waste of space.

Use java.util.BitSet to represent the sieve. It provides a vector of bits that grows as needed. All bits start out as 0, and we can set and clear a bit at any index. It uses only one bit per entry. This requires slightly more computation per access for address computation and bit manipulation, but is much more compact, and utilizes the data cache more efficiently. For larger ranges of integers, we expect memory access time to dominate computation time, making this the ideal solution to represent the sieve.

---

To save additional space and time, at the cost of some additional complexity, we can choose not to represent even integers in our sieve (since they are divisible by 2). Instead, the element at index k will indicate the primarily of the number 2k + 3. We abstract this complexity away by wrapping BitSet in a class exposing special indexer methods.

---

Right now you are using i = i + 2, which could be simplified to i += 2.

---

Final code:

import java.util.BitSet;
import java.util.List;
import java.util.ArrayList;

public class Sieve
{
    private BitSet sieve;

    public Sieve(int size)
    {
        sieve = new BitSet((size + 1) / 2);
    }

    public boolean isComposite(int k)
    {
        assert k >= 3 && (k % 2) == 1;
        return sieve.get((k - 3) / 2);
    }

    public void setComposite(int k)
    {
        assert k >= 3 && (k % 2) == 1;
        sieve.set((k - 3) / 2);
    }

    public static List<Integer> sieveOfEratosthenes(int max)
    {
        Sieve sieve = new Sieve(max + 1); // +1 to include max itself
        for (int i = 3; i * i <= max; i += 2)
        {
            if (sieve.isComposite(i)) continue;

            // We increment by 2*i to skip even multiples of i
            for (int multiplei = i * i; multiplei <= max; multiplei += 2 * i)
                sieve.setComposite(multiplei);
        }

        List<Integer> primes = new ArrayList<Integer>();
        primes.add(2);
        for (int i = 3; i <= max; i += 2)
            if (!sieve.isComposite(i)) primes.add(i);
        return primes;
    }
}

Answer 2

Your method is complex and it has so many local variables. It will be harder for you when you will be de-bugging or reviewing your method.

Final Code

    /**
     * 
     * @param upperLimit
     * @return a list of prime numbers from 0 to upperLimit inclusive
     * @throws IllegalArgumentException if upperLimit is less than 0 
     */
    public static List<Integer> generatePrimes(int upperLimit) {

        if(upperLimit < 0) 
            throw new IllegalArgumentException("Negative size");

        // at first all are numbers (0<=i<=n) not composite
        boolean[] isComposite = new boolean[upperLimit + 1]; 
        for (int i = 2; i * i <= upperLimit; i++) {
            if (!isComposite [i]) {
                // populate all multiples as composite numbers
                for (int j = i; i * j <= upperLimit; j++) {
                    isComposite [i*j] = true;
                }
            }
        }

        List<Integer> primeList = new ArrayList<>();

        // make a list of all non-composite numbers(prime numbers)
        int arrLength = isComposite.length;
        for(int index = 2; index < arrLength; index++) {
            if(!isComposite[index]) {
                primeList.add(new Integer(index));
            }
        }
        return primeList;
    }

---

UPDATE

            if (!isComposite [i]) {
                // populate all multiples as composite numbers
                for (int j = i; i * j <= upperLimit; j++) {
                    isComposite [i*j] = true;
                }
            }

can be improved

            if (!isComposite [i]) {
                for (int j = 2 * i; j <= upperLimit; j += i) {
                    isComposite [j] = true;
                }
            }

Answer 3

I guess I'm confused as to why you would even bother building a list of the prime integers. A BitSet should be far more compact than a list of the integers and can be easily processed for a lot of things.

To check for primeness just directly access that index and you know whether it's prime, or not.

You can also print the list of primes from the BitSet using something similar to what you'd do with the array of integers. You'd just have to check each index for primeness before printing it (not so hard to do).