Introduction

A classic Sieve of Eratosthenes implementation usually uses a boolean array indexed by every number up to n. That breaks down once n grows past 2^32, because the problem is no longer just algorithmic complexity; it is also integer overflow and memory pressure.

Why the Naive Sieve Stops Scaling

Two limits matter immediately.

First, Java int cannot represent values above about 2.1 billion, so code using int for loop bounds or array indexing cannot even address numbers near 2^32, which is about 4.29 billion.

Second, a flat sieve array of size n + 1 is too large for most machines. Even if you use one byte per entry, a sieve up to 2^32 would require several gigabytes of memory before accounting for JVM overhead.

So to go past 2^32, you need two structural changes:

• use long for numeric ranges and arithmetic
• use a segmented sieve so memory stays bounded

The Segmented Sieve Idea

A segmented sieve works in two phases.

First, compute all primes up to sqrt(n) with a normal sieve. That base set is small enough to fit comfortably in memory.

Second, process the range from 2 to n in chunks, such as one million numbers at a time. For each chunk, mark multiples of the base primes, then count or emit the numbers that remain unmarked.

This keeps memory proportional to the segment size instead of proportional to n.

A Runnable Java Example

The code below counts primes up to a long limit using a segmented sieve. It is written to be clear and correct rather than micro-optimized.

1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5public class SegmentedSieve {
6    public static List<Integer> simpleSieve(int limit) {
7        boolean[] isPrime = new boolean[limit + 1];
8        Arrays.fill(isPrime, true);
9        isPrime[0] = false;
10        if (limit >= 1) {
11            isPrime[1] = false;
12        }
13
14        for (int p = 2; (long) p * p <= limit; p++) {
15            if (isPrime[p]) {
16                for (int multiple = p * p; multiple <= limit; multiple += p) {
17                    isPrime[multiple] = false;
18                }
19            }
20        }
21
22        List<Integer> primes = new ArrayList<>();
23        for (int i = 2; i <= limit; i++) {
24            if (isPrime[i]) {
25                primes.add(i);
26            }
27        }
28        return primes;
29    }
30
31    public static long countPrimes(long n) {
32        if (n < 2) {
33            return 0;
34        }
35
36        int root = (int) Math.sqrt(n);
37        List<Integer> basePrimes = simpleSieve(root);
38        int segmentSize = 1_000_000;
39        long count = 0;
40
41        for (long low = 2; low <= n; low += segmentSize) {
42            long high = Math.min(low + segmentSize - 1, n);
43            boolean[] isPrime = new boolean[(int) (high - low + 1)];
44            Arrays.fill(isPrime, true);
45
46            for (int prime : basePrimes) {
47                long start = Math.max((long) prime * prime,
48                        ((low + prime - 1) / prime) * (long) prime);
49
50                for (long multiple = start; multiple <= high; multiple += prime) {
51                    isPrime[(int) (multiple - low)] = false;
52                }
53            }
54
55            for (int i = 0; i < isPrime.length; i++) {
56                if (isPrime[i]) {
57                    count++;
58                }
59            }
60        }
61
62        return count;
63    }
64
65    public static void main(String[] args) {
66        long limit = 10_000_000L;
67        System.out.println(countPrimes(limit));
68    }
69}

The important point is that n is a long, while each segment remains small enough to index with an int array.

Why This Can Go Past 2^32

This design can handle limits larger than 2^32 because it never allocates an array of length n. Only the current segment and the base primes are stored in memory.

That said, "can go past 2^32" does not mean "will be fast enough for arbitrarily huge limits." Runtime still grows with the size of the range, and JVM tuning, CPU cache effects, and disk or output overhead all matter if you print every prime.

For counting primes, segmented sieves are very practical. For storing every prime up to enormous limits, output size itself becomes a serious constraint.

Useful Optimizations

Once the segmented approach is working, common optimizations include:

• skipping even numbers entirely
• using a BitSet or manual bit packing instead of boolean[]
• parallelizing independent segments carefully
• counting only, instead of storing every prime

Skipping evens roughly halves memory and work. Bit packing can reduce memory further, which helps cache efficiency.

Common Pitfalls

The biggest mistake is using int for arithmetic such as p * p or loop bounds. That overflows long before your intended limit.

Another mistake is trying to allocate one giant array anyway. Even if the code compiles, the JVM is likely to run out of heap.

A third issue is starting the marking loop at the wrong multiple inside a segment. If the first multiple is computed incorrectly, the sieve silently produces wrong results.

Finally, printing every prime for very large limits can dominate runtime. Benchmark counting and output separately.

Summary

• A naive sieve does not scale to 2^32 because of both memory usage and int overflow.
• Use long for numeric ranges above the int limit.
• A segmented sieve keeps memory bounded by processing fixed-size chunks.
• The base primes only need to be generated up to sqrt(n).
• Further optimizations include skipping evens and bit packing.
• For very large limits, correctness and memory discipline matter more than clever syntax.