Prime sieve and next prime

How it works

The sieve of Eratosthenes lists all primes up to $N$ without a single division. Write down $2, 3, \dots, N$; the first number, 2, is prime, so cross out its multiples. The next number not crossed out, 3, is prime: cross out its multiples, and so on. Crossing out for $p$ can start at $p^2$, and one can stop once $p^2 > N$: every composite up to $N$ has a prime factor at most $\sqrt N$.

The primes thin out slowly. The prime number theorem says that there are about $N / \ln N$ primes up to $N$ (25 up to 100, 168 up to 1000), so near $n$ about one number in $\ln n$ is prime. That is why finding a 1024-bit prime for RSA is quick: test random odd numbers of that size, and about one in 355 is prime.

For the next or previous prime of a large number, the calculator does just that: it walks through the odd numbers, discards those with a small factor, and checks the survivors with Miller-Rabin.