How Every Prime Number works

The math and engineering behind an infinite list of primes that your own computer calculates as you scroll.

What is a prime number?

A prime is a whole number greater than 1 that can only be divided evenly by 1 and itself. 2, 3, 5, 7, 11 and 13 are prime. 12 is not, because 12 = 3 × 4. Every whole number above 1 is either prime or a product of primes, which is why primes are often called the atoms of arithmetic.

Why you only need to check divisors up to √n

The obvious way to test whether n is prime is to try dividing it by every number below it. You can stop much sooner. If n isn’t prime, it splits into two factors, and they can’t both be bigger than √n:

So if nothing up to √n divides n, nothing above it will either: its partner factor would have been found already. To test 1,000,003 you only need to try divisors up to 1,000. You can go further and try only prime divisors, since any composite divisor would have been caught by one of its prime factors first.

How the sieve of Eratosthenes works

Testing numbers one at a time repeats a lot of work. The sieve of Eratosthenes, over two thousand years old, finds all the primes up to a limit at once, and it never divides anything:

1. Write down every number from 2 up to the limit.
2. Take the first number not yet crossed off. It’s prime.
3. Cross off all its multiples, starting from its square. Smaller multiples were already crossed off by smaller primes.
4. Repeat until the next prime squared is past the limit. Everything left is prime.

The catch is memory: you need one slot for every number up to the limit. Sieving to a trillion that way would take a trillion slots.

How the segmented sieve of Eratosthenes works

The segmented sieve fixes that by sieving one fixed-size window, a segment, at a time. To find the primes in a range [low, high):

1. Find the base primes: every prime up to √high. By the √n rule, these are the only divisors that matter for anything in the range. They are few: the primes below 1,000,000 are enough for every number up to a trillion.
2. For each base prime, jump straight to its first multiple inside the segment and cross off every multiple from there to the end.
3. Whatever survives is prime.

A small worked example: the primes from 100 to 119.

• √119 is just under 11, so the base primes are 2, 3, 5 and 7.
• 2 crosses off 100, 102, 104, …, 118.
• 3 starts at 102 (the first multiple of 3 from 100) and crosses off 102, 105, 108, 111, 114, 117.
• 5 crosses off 100, 105, 110, 115.
• 7 starts at 105 and crosses off 105, 112, 119.
• The survivors are 101, 103, 107, 109 and 113, the five primes in that range.

In code, one segment looks roughly like this:

// The primes in [low, high), given every prime up to √high.
function sieveSegment(low, high, basePrimes, isComposite) {
  isComposite.fill(0, 0, high - low); // reuse one buffer for every segment
  for (const prime of basePrimes) {
    if (prime * prime >= high) break;
    // First multiple of prime inside the segment, but never below prime².
    const firstMultiple = Math.max(prime * prime, Math.ceil(low / prime) * prime);
    for (let multiple = firstMultiple; multiple < high; multiple += prime) {
      isComposite[multiple - low] = 1;
    }
  }
  const primes = [];
  for (let candidate = Math.max(low, 2); candidate < high; candidate++) {
    if (!isComposite[candidate - low]) primes.push(candidate);
  }
  return primes;
}

This is how the site’s background worker finds primes. Memory stays flat because the scratch buffer is the same size for every segment, wherever it is on the number line. Only the list of base primes grows, and it grows very slowly, so the worker keeps it and extends it only when the numbers get big enough to need a new base prime.

A batch on the site is always 500 primes, not a fixed range of numbers. Primes thin out as numbers grow, so the bigger the numbers, the more segments the worker has to sieve to collect 500 of them.

How an infinite scroll can use constant memory

You can scroll forever, but the page never holds more than 1,500 primes. They live in a rolling buffer of three batches of 500:

• Scroll down until the bottom of the screen is 60% of the way through the last batch, and the worker is asked for the next 500 primes. When they arrive, they’re added at the end and the first batch is dropped.
• Scroll up until the top of the screen is 60% of the way back through the first batch, and the 500 primes before it are requested. They’re added at the start and the last batch is dropped. At 2 it stops: there’s nothing before it.
• When a batch is dropped from the top or added above you, every row below it moves. The list moves its scroll position by exactly the same amount, so the primes on screen don’t jump.

Scrolling back up recomputes primes the page has already seen, on purpose. Storing them all would make memory grow forever. Recomputing keeps memory flat and only costs CPU, which is the whole point of the site anyway. Only the rows near the screen are actually drawn, so the number of elements on the page stays small too.

The worker only computes when the buffer asks for more, so it never races ahead into numbers nobody has scrolled to. When it is working, it runs flat out in a background thread, so the page stays responsive.

How many primes are there below x?

Mathematicians write π(x) (nothing to do with 3.14159…) for the number of primes up to x. π(10) = 4, because of 2, 3, 5 and 7. There’s no neat formula for π(x), but there is a famously good approximation, the logarithmic integral:

The idea behind it: near a number t, roughly one number in every ln t is prime. Add up those chances from 0 to x and you get the expected count. It’s remarkably close. At a trillion:

The simpler x / ln x is what you often see quoted, but it’s about 37,000 times further off here.

See it live: jump to a trillion →

Computing li(x) with Ramanujan’s series

The integral above can’t be computed directly with a calculator button. The site uses a series found by Srinivasa Ramanujan, which converges quickly for any x:

Here γ ≈ 0.5772 is the Euler–Mascheroni constant. It looks fearsome, but it’s a loop. Each term reuses the previous one, so there are no giant powers or factorials:

const lnX = Math.log(x);
let sum = 0;
let powerOverFactorial = 1; // (ln x)^n / (n! · 2^(n−1))
let oddReciprocalSum = 0;   // 1 + 1/3 + 1/5 + …

for (let n = 1; n <= 200; n++) {
  powerOverFactorial *= n === 1 ? lnX : lnX / (2 * n);
  if (n % 2 === 1) oddReciprocalSum += 1 / n;
  const term = (n % 2 === 1 ? 1 : -1) * powerOverFactorial * oddReciprocalSum;
  sum += term;
  if (n > lnX && Math.abs(term) < Number.EPSILON * Math.abs(sum)) break;
}
return EULER_MASCHERONI + Math.log(lnX) + Math.sqrt(x) * sum;

The site’s tests check it against known values: li(10⁶) ≈ 78,627.5, li(10⁹) ≈ 50,849,234.9 and li(10¹²) ≈ 37,607,950,280.8, all to within 0.1.

How the site estimates a prime’s position after a jump

Next to each prime the list shows its position: 2 is #1, 3 is #2, and so on. Scrolling from the start, that’s just counting. But when you jump to, say, a trillion, the site has no idea how many primes it skipped. Counting them exactly would mean finding all 37.6 billion of them.

So it estimates, once. The first prime the jump finds (the anchor) gets li(anchor), rounded. Every other row counts exactly up or down from the anchor, so neighbouring labels always differ by exactly 1. The estimate is shown with a “≈”, and a banner above the list says so. Jumping to a trillion lands on 1,000,000,000,039, labelled ≈ #37,607,950,282. That’s about 38,000 too high: roughly 0.0001% off.

Scroll all the way back down to 2 and the buffer finally knows exactly where it is: the “≈” and the banner disappear and every label becomes exact.

Try it: jump to a billion and look for the “≈” →

What is the largest number JavaScript can store exactly?

JavaScript numbers are 64-bit floating point. They store whole numbers exactly only up to

That’s Number.MAX_SAFE_INTEGER. Past it, numbers start rounding: 2**53 + 1 comes out as 9,007,199,254,740,992. A prime finder that silently rounds would show wrong primes, which is worse than showing none. So the site refuses: the jump box won’t accept anything from 2⁵³ − 1 up, and if scrolling ever reaches it, the worker stops and the page announces that you broke math.

Why measuring speed in a browser is harder than it looks

The primes-per-second counter is the joke of the site: it starts huge and sinks as the numbers grow. Measuring it honestly turned out to be tricky.

Browsers deliberately round performance.now(), because precise timers can be used for fingerprinting and for timing attacks like Spectre. Without special setup, the steps are often 0.1 ms or coarser. Early batches of small primes finish faster than that, so a single batch usually measures 0 ms, or one whole step. Dividing 500 primes by a duration that’s mostly rounding error gives a counter that leaps around by 10×.

Two fixes:

• Average over a window. The counter divides the total primes from recent batches by their total measured time, keeping enough batches to cover at least 50 ms (and at most 32 batches, so it still reacts when things slow down). Batches that measured 0 ms still count. Across many batches the rounding evens out.
• Cross-origin isolation. The site sends the Cross-Origin-Opener-Policy and Cross-Origin-Embedder-Policy headers. In exchange for only loading resources it’s allowed to, the page gets a much finer timer. In Chrome it went from 0.1 ms steps to 0.005 ms.

The counter measures compute time, not wall-clock time: when you stop scrolling, the worker rests and the counter keeps its last value instead of sinking to zero.

Fun facts about prime numbers

Why are there infinitely many primes?

Euclid proved it around 300 BC, and the proof still fits on a napkin. Suppose there were only finitely many primes, p₁, p₂, …, pₖ. Multiply them all together and add 1:

1. Dividing N by any of the primes on the list leaves a remainder of 1.
2. So no prime on the list divides N.
3. But N is bigger than 1, so it has at least one prime factor (maybe N itself).
4. That prime isn’t on the list, so the list wasn’t complete after all.

Any finite list of primes is missing one, so there are infinitely many. Which is why a site called Every Prime Number is a joke with no punchline: you can scroll forever and never finish.

What is the Ulam spiral?

In 1963, the mathematician Stanisław Ulam was doodling during a dull talk. He wrote the numbers in a square spiral, starting from 1 in the middle, and circled the primes. They didn’t scatter randomly. They clumped along diagonal lines:

Each diagonal in the spiral is the set of values of a quadratic like 4n² + 2n + 1. Some quadratics can never be prime (for instance, if they’re always even), and others turn out to hit primes unusually often. Euler’s n² + n + 41 is prime for every n from 0 to 39. The lines are those prime-rich quadratics showing through.

The prime number theorem in plain English

Primes get rarer as numbers grow, but in a very predictable way. Around a number x, about one number in every ln x is prime: about one in 7 near a thousand, one in 14 near a million, one in 28 near a trillion. That’s the prime number theorem, proved in 1896 by Jacques Hadamard and Charles de la Vallée Poussin independently, and it’s the reason the counter on the home page slows down: the further you go, the more numbers the worker has to throw away for each prime it finds.

Prime gaps and twin primes

The gap between one prime and the next tends to grow, roughly like ln x on average, but it keeps dropping back to 2. Pairs of primes that differ by 2, like 11 and 13 or 1,000,000,000,061 and 1,000,000,000,063, are twin primes. The twin prime conjecture says there are infinitely many of them. Nobody has proved it. The closest result: in 2013 Yitang Zhang proved that some gap of at most 70 million occurs infinitely often, and collaborative work soon brought that bound down to 246.

See that twin prime pair just past a trillion →

Goldbach’s conjecture

Every even number greater than 2 seems to be the sum of two primes: 4 = 2 + 2, 28 = 5 + 23, 100 = 3 + 97. Christian Goldbach suggested it in a letter to Euler in 1742. It has been checked by computer for every even number up to 4 × 10¹⁸, and it is still unproved.

The Riemann hypothesis and how far li(x) can be off

The site leans on li(x) being close to π(x). How close is it guaranteed to be? That depends on the most famous unsolved problem in mathematics. If the Riemann hypothesis is true, then for every x ≥ 2,657:

That bound is Lowell Schoenfeld’s (1976). At a trillion it allows an error of about 1.1 million; the real error is 38,263. Without the Riemann hypothesis, the proven bounds are much weaker. One more twist: li(x) is bigger than π(x) for every x anyone has checked, but J. E. Littlewood proved in 1914 that the two swap places infinitely often. The first swap is somewhere far beyond anything a computer could reach by counting.

Mersenne primes and the largest known prime

A Mersenne number is one less than a power of two, 2ᵖ − 1. For it to be prime, p has to be prime, but that isn’t enough: 2¹¹ − 1 = 2047 = 23 × 89. Mersenne numbers have a very fast special-purpose primality test (the Lucas–Lehmer test), so the largest known primes are almost always Mersenne primes.

The record holders are found by the Great Internet Mersenne Prime Search (GIMPS), a volunteer project running since 1996 on thousands of ordinary computers. The current record is listed at mersenne.org. It would take this site a little longer to scroll there.

Where are prime numbers used? RSA encryption

Every time you load a page over HTTPS, primes may be doing the work. RSA encryption builds a public key by multiplying two enormous secret primes. Multiplying them is instant, but splitting the product back into its two primes is so slow for numbers that size that, as far as anyone knows, no computer can do it in a useful amount of time.

Want to see it in action? Start scrolling, or read about the site.