Finding the Billionth Prime in Under One Second

There's a particular kind of intellectual honesty in announcing your goal is to find the billionth prime number in under a second, and then spending twenty-eight minutes showing you exactly how many wrong turns you took getting there. That's roughly what the creator of Sheafification of G does in a recent video—and the wrong turns are, genuinely, the interesting part.

The premise is deceptively clean: implement a function that takes an integer n and returns the nth prime, then see how large an n you can handle in under a second. No precomputed lookup tables allowed. Everything computed dynamically, from scratch, on a standard machine. The implementation language is LLVM intermediate representation—hand-written, not compiler-generated—which is either an act of purity or masochism depending on your disposition toward assembly-adjacent code.

Where You Start (And Why It Fails)

The naïve approach is to iterate through integers and check each one for primality. The naïve primality check loops through every candidate divisor up to p itself. As the video puts it, this is "called the naive iteration method for a reason." The result: the 11,319th prime. Not terrible for a first attempt. Not remotely close to a billion.

The first real improvement—checking divisors only up to √p rather than p itself—is mathematically trivial but practically dramatic. If a number has no divisor smaller than its square root, it has no divisors at all (other than itself and one). This single observation pushes the counter to the 343,620th prime, a 30× improvement. That ratio should give you some intuition for how punishing even modest algorithmic complexity becomes at scale.

From there, the video reaches for the Miller-Rabin primality test—a probabilistic algorithm that grows logarithmically in its input, compared to the square-root growth of the trial division approach. Miller-Rabin works by writing p−1 as 2^s × d (where d is odd), then selecting random witnesses a and checking whether certain modular exponentiations pass. If a number is composite, at least one in four random witnesses will catch it. The probabilistic element gets resolved by a known result from Jaeschke (1993): for numbers below roughly 3.2 × 10¹⁸, a specific fixed set of witnesses—{2, 13, 23, 1,662,803}—makes the test deterministic. No gambling required.

The result: past the 480,000th prime. Which is actually less than the square-root sieve found. This is the video's first real pedagogical gut-punch.

The Lens Shift That Changes Everything

Hyper-optimizing the primality test turns out to be the wrong frame entirely. The goal isn't "efficiently check if one number is prime." The goal is "find the nth prime." These sound similar but have different optimal strategies.

"Hyperfocusing on optimizing the primality test makes it easy to forget that what we're actually trying to do is find the nth prime number, not check if an arbitrary integer is prime," the video notes. The better approach doesn't ask whether each candidate is prime—it asks which candidates can be ruled out en masse as composites.

This is the Sieve of Eratosthenes, or rather a family of sieve methods, and the shift from individual testing to bulk elimination is where the real performance gains live. The idea is old: mark every multiple of 2 as composite, then every multiple of 3, then 5, and so on. Whatever survives is prime. The catch is bounding the sieve—you need to know roughly where the nth prime lives before you can build a sieve up to it. The Prime Number Theorem, via Rosser and Schoenfeld's 1962 bounds, gives you p(n) < n(ln n + ln ln n), which the video approximates using bit-length arithmetic instead of floating-point logarithms. Clever, and the resulting bound is good enough to work with.

The naive sieve implementation clears the 5.5 millionth prime. One small fix—starting composite marking at p² rather than 2p, since all smaller multiples of p have already been handled by smaller primes—brings it to 7.5 million. Then bit-packing the sieve array to count primes in 64-bit chunks via popcount gets it to 8.3 million.

None of these changes improve the asymptotic complexity. But none of them need to, yet.

The Cache Problem Nobody Tells You About in Algorithms Class

Around the 4-million-prime mark, something happens in the runtime graphs: they bend. The gentle slope of early performance suddenly steepens. This isn't an algorithmic failure—it's hardware.

Modern CPUs use a hierarchy of caches: L1 (fast, small—32KB is typical), L2 (slower, larger), L3 (slower still, much larger), then main RAM (devastatingly slow by comparison). "An L3 read is up to 20 times slower than an L1 read," the video notes. When your sieve array fits in L1, everything is fast. When it spills into L2, slower. When it spills into L3, the runtime graph breaks sharply upward.

The fix is the segmented sieve: instead of maintaining one giant sieve, maintain a small sieve segment that fits in L1 cache, process it completely—marking all composites using a precomputed list of small primes—then discard it and move to the next segment. Since you're only interested in counting primes (to find the nth one), you don't even need to write segments back to larger memory. Just count, discard, continue.

The segmented sieve hits 22.8 million primes. Then another counterintuitive move: switching from one bit per sieve entry to one byte per sieve entry. Sounds wasteful. Actually faster. Because flipping a single bit in memory requires a read-modify-write cycle (read the byte, flip the bit, write the byte back), while overwriting a whole byte is a single write operation. The extra memory fits fine within the segment structure. This pushes past 34 million.

Where Theory Loses to Hardware

The video then attempts Pritchard's wheel sieve—a 1981 algorithm designed to mark each composite number exactly once, giving sublinear runtime in the sieve size. On paper, this is the asymptotically superior choice. In practice, it lands at 3.1 million primes.

The culprit is data structure choice. Pritchard's algorithm requires frequent insertions into and deletions from a growing set, which sounds like a job for a linked list—fast O(1) insertion and deletion. The problem is that linked lists are spatially incoherent: their elements scatter across memory, making sequential traversal a cache massacre. Every pointer-follow is potentially an L3 (or RAM) lookup.

"The reality of the linked list is that it is only good at fast insertion and deletion and is immediately a bad choice of data structure the moment you need to iterate over its elements," the video explains. Switching to a contiguous array restores cache-friendly traversal but makes deletion expensive again. The video's workaround—batch deletions within each wheel iteration—improves Pritchard's implementation enough to outperform the basic sieve of Eratosthenes (16.7 million primes), but the segmented byte sieve still wins handily.

This tension—between what's theoretically optimal and what performs on actual silicon—runs through the entire video. Big-O analysis assumes a uniform-cost memory model where every read takes the same time. Real computers don't work that way. The memory hierarchy means that data locality can matter more than algorithmic complexity, within the ranges we're actually working in.

It's a lesson that's genuinely hard to convey in an algorithms course, where cache effects are typically waved away as implementation details. They're not. When your problem size crosses a cache boundary, your runtime can jump by a factor of twenty without a single line of your algorithm changing.

The billionth prime, for reference, is 22,801,763,489. Getting there in under a second requires finding it algorithmically—no precomputation, no table lookup—which means navigating this exact landscape of mathematical theory, data structure tradeoffs, and hardware realities simultaneously.

But the path there is, in an odd way, more useful than the destination—because the same tradeoffs show up everywhere computational scientists push against time limits.

---

By Amelia Nwofor, Science Desk Editor