Prime Number Generator: List, Test and Find Primes

About the Prime Number Generator

The Prime Number Generator answers the five questions people ask about primes. It lists all the primes between two numbers, lists the first n primes, tells you whether a number is prime and, if it is not, which prime divides it first, finds the n-th prime, and draws random primes with a chosen number of digits or from a chosen range. A prime is a whole number greater than 1 whose only divisors are 1 and itself, so 2, 3, 5, 7 and 11 are prime and 1 is not.

Lists can be shown separated by commas, spaces or new lines, copied with one click and saved as a .txt file. Ranges may reach 1,000,000,000,000 and span up to 10,000,000 numbers. At most 10,000 primes are displayed; when a range holds more, the page tells you how many there are in total. Big jobs run in a background worker, so the page stays responsive while it works.

How to use it

How the answers are found

Lists use the sieve of Eratosthenes. The page crosses out every multiple of 2, 3, 5 and each prime up to the square root of the end of the range, and what is left is prime. For ranges far from zero it sieves only the window you asked for, which is why 999,999,999,900 to 1,000,000,000,000 is as quick as any other 100 numbers.

The primality test uses the Miller-Rabin test with the first thirteen primes, 2 to 41, as bases. That choice is deterministic for every number below $3.3 \times 10^{24}$, so it is exact, not probabilistic, for the whole range of the primality test. When a number is composite, the page finds its smallest prime factor by trial division and, for large numbers, Pollard's rho method.

The n-th prime sieves up to the bound

$$p_n < n\,(\ln n + \ln\ln n) \quad (n \ge 6)$$

and counts primes until it reaches the n-th, so the one millionth prime, 15,485,863, takes a fraction of a second.

Random primes are drawn uniformly. For a range of fewer than 100,000 numbers the page lists every prime in it and picks from that list, so a small range never repeats a prime and says so when it holds fewer primes than you asked for. For longer ranges, such as all 30-digit numbers, it picks random numbers in the range and keeps those that pass Miller-Rabin. Above 3.3 × 10²⁴ the test uses twenty bases and is probabilistic: a composite has less than one chance in 4²⁰ of passing. Searches above 12 digits run in the background worker.

Worked examples

• Primes up to 30: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. There are 10 of them.
• Is 91 prime? No. 91 = 7 × 13, so its smallest prime factor is 7, even though 91 is not divisible by 2, 3 or 5.
• How many primes are below one million? 78,498.
• Is 4,294,967,297 prime? No, it equals 641 × 6,700,417, which is why 2^32 + 1 is not a Fermat prime.
• The largest prime below 2^64 is 18,446,744,073,709,551,557.

Why 1 and 0 are not prime

A prime must have exactly two divisors. The number 1 has one and 0 has infinitely many, so neither is prime. They are not composite either; the page says "neither prime nor composite" for them.

Privacy

Nothing is uploaded; every calculation runs in your browser and never leaves your device. The numbers you type are not stored.

Related tools

Use the Random Number Generator to pick numbers at random. The Number List Calculator adds up and averages a list of primes you copy from here. The Fibonacci Generator lists another famous sequence, and its prime terms are a good test for the primality check here. To split a composite number into all of its prime factors, use the Prime Factorization Calculator.

Open-source credits

• The generator is written for this site and uses no third-party library. The sieve of Eratosthenes, the Miller-Rabin test (G. L. Miller, 1976; M. O. Rabin, 1980) and Pollard's rho method (J. M. Pollard, 1975) are implemented in-house on the browser's built-in BigInt.
• The deterministic bound for the first thirteen prime bases is from J. Sorenson and J. Webster, Strong pseudoprimes to twelve prime bases (Mathematics of Computation, 2017), and the n-th prime bound is Rosser's theorem.

Frequently asked questions