Java With Us

Sieve of Eratosthenes in Java

Updated on 2026-04-20 Reviewed by the Java With Us editorial team

The Sieve of Eratosthenes is a classic algorithm for finding all prime numbers up to a given limit. Invented by the Greek mathematician Eratosthenes around 250 BC, it remains one of the fastest approaches in practice for moderate limits.

The idea

Rather than testing each candidate individually, the sieve eliminates composites systematically:

  1. List all integers from 2 to n.
  2. Mark the first unmarked number (initially 2) as prime.
  3. Cross out all multiples of that prime.
  4. Move to the next unmarked number and repeat.
  5. Stop when the current number exceeds sqrt(n). Every unmarked number is prime.

Basic Java implementation

public class Sieve {

    public static boolean[] sieve(int n) {
        boolean[] isComposite = new boolean[n + 1];
        isComposite[0] = isComposite[1] = true; // 0 and 1 are not primes

        for (int i = 2; (long) i * i <= n; i++) {
            if (!isComposite[i]) {
                // Start crossing out from i*i — smaller multiples already marked
                for (int j = i * i; j <= n; j += i) {
                    isComposite[j] = true;
                }
            }
        }
        return isComposite;
    }

    public static void main(String[] args) {
        int n = 50;
        boolean[] composite = sieve(n);
        StringBuilder primes = new StringBuilder("Primes up to " + n + ": ");
        for (int i = 2; i <= n; i++) {
            if (!composite[i]) primes.append(i).append(' ');
        }
        System.out.println(primes);
    }
}
// → Primes up to 50: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Why start at i*i?

Any composite smaller than i*i has a prime factor smaller than i, and was therefore already crossed out by a previous iteration. Starting the inner loop at i*i is a constant-factor speed-up and avoids redundant work.

Using a BitSet for memory efficiency

For large n, an array of boolean consumes 1 byte per element. A BitSet uses one bit — eight times less memory:

import java.util.BitSet;

public static BitSet sieveBitSet(int n) {
    BitSet composite = new BitSet(n + 1);
    composite.set(0);
    composite.set(1);
    for (int i = 2; (long) i * i <= n; i++) {
        if (!composite.get(i)) {
            for (int j = i * i; j <= n; j += i) {
                composite.set(j);
            }
        }
    }
    return composite;
}

A 100-million-entry sieve fits in roughly 12 MB with BitSet versus 100 MB with boolean[].

Only odd numbers (half the memory)

Every even number except 2 is composite, so we can skip them entirely. This halves memory and time:

public static int[] primesUpTo(int n) {
    if (n < 2) return new int[0];
    // Index i represents the odd number 2*i + 1. Size = (n/2) + 1.
    int size = (n - 1) / 2 + 1;
    boolean[] composite = new boolean[size];
    for (int i = 1; (long)(2*i + 1) * (2*i + 1) <= n; i++) {
        if (!composite[i]) {
            int p = 2 * i + 1;
            for (long j = (long) p * p; j <= n; j += 2 * p) {
                composite[(int)((j - 1) / 2)] = true;
            }
        }
    }
    int[] primes = new int[size + 1];
    int k = 0;
    primes[k++] = 2;
    for (int i = 1; i < size; i++) {
        if (!composite[i]) primes[k++] = 2 * i + 1;
    }
    return java.util.Arrays.copyOf(primes, k);
}

Complexity

  • Time: O(n log log n) — remarkably close to linear.
  • Space: O(n) bits, O(n) booleans or O(n/8) with BitSet.

In practice, the basic sieve handles n up to tens of millions in under a second on a modern machine.

Segmented sieve (for very large n)

When n is too large to hold all of isComposite[] in memory (say, n = 1012), split the range into cache-friendly segments and sieve each one using only the primes up to sqrt(n):

public static void segmentedSieve(long n) {
    int limit = (int) Math.sqrt(n) + 1;
    boolean[] small = sieve(limit);
    List<Integer> basePrimes = new ArrayList<>();
    for (int i = 2; i < limit; i++) if (!small[i]) basePrimes.add(i);

    long segmentSize = 1 << 16; // 64 KB segments
    boolean[] segment = new boolean[(int) segmentSize];

    for (long low = limit; low <= n; low += segmentSize) {
        long high = Math.min(low + segmentSize - 1, n);
        java.util.Arrays.fill(segment, false);
        for (int p : basePrimes) {
            long start = Math.max((long) p * p, ((low + p - 1) / p) * p);
            for (long j = start; j <= high; j += p) segment[(int)(j - low)] = true;
        }
        for (long i = low; i <= high; i++) {
            if (!segment[(int)(i - low)]) {
                // emit i (or count, or whatever)
            }
        }
    }
}

Beyond the sieve

  • For primality testing of a single huge number, use BigInteger.isProbablePrime(certainty) which runs Miller-Rabin.
  • For prime counting up to 1012, consider more advanced algorithms (Meissel-Mertens, Legendre).
  • For a stream of primes, a linear sieve (Euler's sieve) runs in strict O(n) with a few more arithmetic operations.

The Sieve of Eratosthenes is a beautiful example of how a simple idea — cross out multiples — yields a surprisingly fast algorithm. For any real-world prime generation up to a few hundred million, it is the right choice.

Related articles