Sieve of Eratosthenes. Adopted from http://en.literateprograms.org/Sieve_of_Eratosthenes_(Java)

Sieve.java

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

public class Sieve {
    private BitSet sieve;

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

    private boolean is_composite(int k) {
        assert validIdx(k);
        return sieve.get(index(k));
    }

    private int index(int k) {
        return (k - 3) / 2;
    }

    private boolean validIdx(int k) {
        return k >= 3 && (k % 2) == 1;
    }

    private void set_composite(int k) {
        assert validIdx(k);
        sieve.set(index(k));
    }

    public static List<Integer> sieve_of_eratosthenes(int max) {
        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);
            }
        }

        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;
    }

}