Primes in a Range

The calculator automatically chooses between a segmented sieve and direct primality testing based on the size and width of the interval. Computation runs locally in your browser.

For ordinary ranges, the calculator uses a segmented sieve of Eratosthenes. The interval is processed in blocks, and candidates divisible by 2, 3, and 5 are omitted using a wheel (only the 8 residues coprime to 30 are stored). The base primes up to √U are found once and used to strike out composites in each block. The result is exact.

For narrow ranges around very large integers, generating every prime up to √U would be impractical. In that case the calculator presieves the candidates by small primes and tests the survivors with the site's primality engine. Below 2⁶⁴ it uses a Baillie–PSW test, which is known to have no exceptions in that range; from 2⁶⁴ up to B = 3,317,044,064,679,887,385,961,981 it uses deterministic Miller–Rabin with the first 13 prime bases. Results in both ranges are proven primes. From B up it uses a Baillie–PSW test, and the results are probable primes.

Results are labeled probable primes when primality is not deterministically proved. The method is chosen from the size of U and the width of the interval using a cost model measured on real runs; it never changes the answer, only how fast it is found. Long searches are divided among several background workers, each taking one part of the interval. The page lists the first 1,000 results; the complete result of a finished search can be downloaded as a text file with one prime per line (up to 10,000,000 results). Ranges whose predicted work exceeds the calculator's browser work limit are refused with a message rather than started.