Sieve of Eratosthenes (Java)

From LiteratePrograms

Other implementations: Alice ML | Bash | C++ | Forth | Haskell | Java | Python | Python, arrays | Scala

The Sieve of Eratosthenes is an algorithm for rapidly locating all the prime numbers in a certain range of integers. It operates by marking as composite all nontrivial multiples of each prime in sequence until only primes remain unmarked. It is most well-suited to implementation using arrays, which are compact and feature random access.

Contents 1 Design 2 Main implementation 3 Test driver 4 Files

Design

We have several portable choices for representing the sieve in Java:

• boolean[]: an array of booleans. Each boolean is set to false or true to indicate prime or composite, respectively. However, internally, each boolean is usually stored as a byte (8 bits), which is a waste of space.
• java.util.BitSet: 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.

Main implementation

To save additional space and time, at the cost of some additional complexity, we choose not to represent even integers in our sieve. 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:

<<Sieve class>>=
public class Sieve
{
    private BitSet sieve;
    public Sieve(int size) {
        sieve = new BitSet((size+1)/2);
    }
    public boolean is_composite(int k)
    {
        assert k >= 3 && (k % 2) == 1;
        return sieve.get((k-3)/2);
    }
    public void set_composite(int k)
    {
        assert k >= 3 && (k % 2) == 1;
        sieve.set((k-3)/2);
    }
    sieve of Eratosthenes
    main method
}

The standard library classes BitSet, List, and ArrayList are imported for convenience in later use:

<<imports>>=
import java.util.BitSet;
import java.util.List;
import java.util.ArrayList;

The sieve itself begins by creating a sieve array and then searching for the first zero entry. All odd multiples of this entry are set to true to indicate that they are composite. We start with the square i*i of i, because all multiples of i smaller than that will have already been set to true while dealing with smaller primes. Note that by default a BitSet is initialized to all zeros, as the algorithm requires.

<<sieve of Eratosthenes main body>>=
Sieve sieve = new Sieve(max + 1); // +1 to include max itself
for (int i = 3; i*i <= max; i += 2) {
    if (sieve.is_composite(i))
        continue;
    // We increment by 2*i to skip even multiples of i
    for (int multiple_i = i*i; multiple_i <= max; multiple_i += 2*i)
        sieve.set_composite(multiple_i);
}

When we're done, we iterate through the sieve, forming an ArrayList of elements still set to false, which we return:

<<sieve of Eratosthenes>>=
public static List<Integer> sieve_of_eratosthenes(int max)
{
    sieve of Eratosthenes main body
    List<Integer> primes = new ArrayList<Integer>();
    primes.add(2);
    for (int i = 3; i <= max; i += 2)
        if (!sieve.is_composite(i))
            primes.add(i);
    return primes;
}

Test driver

We included in the Sieve class a main method that takes a maximum value on the command-line, determines the time required for the computation in total and per integer, and writes out the resulting list of primes. We offer an optional second parameter indicating the number of times to repeat the sieve, for better precision in the time measurement.

<<main method>>=
public static void main(String[] args)
{
    int max = 1;
    int num_times = 1;
    if (args.length > 0)
        max = Integer.parseInt(args[0]);
    if (args.length > 1)
        num_times = Integer.parseInt(args[1]);
    List<Integer> result = null;
    long start_time = System.currentTimeMillis();
    for (int i = 0; i < num_times; i++)
        result = sieve_of_eratosthenes(max);
    double time_in_ms = (double)(System.currentTimeMillis() - start_time) / num_times;
    double time_per_integer_ns = time_in_ms / max * 1000000;
    System.out.println("Sieved over integers 1 to " + max + " in "
                       + time_in_ms + " ms (" + time_per_integer_ns + " ns per integer)");
    for (Integer i : result) 
        System.out.println(i);
}

Files

We place the Sieve class in a file with the same name. The implementation of the sieving in included in the class.

<<Sieve.java>>=
imports
Sieve class

Download code