Introduction
Generating prime numbers by hand stops being practical somewhere around the five-digit range. If you need the first 10,000 primes, or want to test whether a 40-digit number is prime, you need an algorithm, not a calculator. This prime number generator runs entirely in your browser, producing primes via the Sieve of Eratosthenes and testing large candidates with the Miller-Rabin probabilistic test. No data leaves your machine. Paste a number, pick a mode, and get results instantly. The tool handles BigInt inputs, so you can test numbers far beyond JavaScript's native integer limit.
What this tool does
- Generate all primes within a numeric range (e.g. all primes between 1,000 and 10,000)
- Find the first N primes starting from 2, up to 100,000 primes in a single run
- Test any positive integer for primality using Miller-Rabin with BigInt (no size limit)
- Use deterministic witnesses for numbers below 3.3 x 10^24 (the first 13 primes), giving a proven result
- Find the next prime after any number, or generate N consecutive primes from a starting point
- Run the Sieve of Eratosthenes up to 1,000,000 and display count, largest prime, and paginated results
- Copy any result list to your clipboard with one click
How this tool works
The tool exposes four modes via tabs. The Generate tab finds primes either within a range or as the first N primes, using an optimized Sieve of Eratosthenes backed by a Uint8Array for memory efficiency. The Primality Test tab accepts arbitrarily large numbers as BigInt. For numbers below 2^32, it applies trial division up to the square root, which is deterministic. For larger inputs, it runs the Miller-Rabin test: it decomposes n-1 into 2^r * d, then tests witnesses. If n is below 3,317,044,064,679,887,385,961,981, the first 13 primes serve as witnesses and the result is provably correct. Above that bound, the tool uses 40 random witnesses, yielding an error probability below 2^-80. The Next Prime tab increments candidates and tests each one until a prime is found. The Sieve tab runs the classic algorithm up to your chosen limit (capped at 1,000,000 for browser performance) and paginates the output. All computation happens client-side in JavaScript.
How prime number generation works
Prime numbers are integers greater than 1 with exactly two divisors: 1 and themselves. The Sieve of Eratosthenes, attributed to the Greek mathematician Eratosthenes of Cyrene around 200 BCE, remains the most efficient way to enumerate all primes up to a fixed limit. It works by iteratively marking multiples of each prime, starting at 2. The unmarked numbers that remain are prime. Its time complexity is O(n log log n).
For testing a single large number, trial division (checking divisibility up to sqrt(n)) is too slow. The Miller-Rabin test, published by Michael Rabin in 1980 (building on Gary Miller's 1976 work), is a probabilistic alternative. It relies on the fact that for a prime n, certain exponentiation properties always hold. A composite number may pass these checks for some bases (called strong liars), but for random bases the probability of a false positive drops by at least 3/4 per round. With 40 rounds, the error probability is below 2^-80. For numbers below 3.3 x 10^24, a fixed set of 13 small primes as witnesses gives a deterministic answer, as proven by Sorenson and Webster (2015).
The Prime Number Theorem tells us that the density of primes near x is approximately 1/ln(x), so primes become rarer as numbers grow but never run out. NIST SP 800-89 recommends specific primality testing methods for cryptographic key generation, including probabilistic tests with sufficient rounds for the required security level.
How to use this tool
- Open the tab for the mode you need: Generate Primes, Primality Test, Next Prime, or Sieve of Eratosthenes
- For Generate: enter a minimum and maximum (range mode) or a count (first N mode), then click Generate
- For Primality Test: type any positive integer (BigInt supported, no size limit) and click Test Primality
- For Next Prime: enter a starting number and how many consecutive primes you want, then click Find
- For Sieve: enter an upper limit (max 1,000,000) and click Run Sieve to see all primes up to that limit
- Review the results: counts, timing, and the prime list itself are shown in a scrollable area
- Click Copy to copy the prime list or a page of primes to your clipboard
Real-world examples
Generating RSA key candidates
When implementing RSA, you need two large primes p and q. Enter a random 512-bit number into the Primality Test tab to check if it is prime. If composite, switch to the Next Prime tab with that number as the start, and find the next prime. This mirrors how real RSA key generators work: pick a random odd number, test it, and if composite, increment by 2 and test again.
Counting primes up to 1,000,000
Open the Sieve tab, enter 1000000 as the limit, and click Run Sieve. The tool finds 78,498 primes in under 100 milliseconds, with the largest being 999,983. This matches the known count of primes below one million. The Prime Number Theorem approximation (n / ln(n)) gives roughly 72,382, showing the theorem underestimates slightly at this scale.
Testing a Mersenne number
Mersenne primes are primes of the form 2^p - 1. Enter 170141183460469231731687303715884105727 (which is 2^127 - 1) into the Primality Test tab. The tool confirms it is prime using deterministic Miller-Rabin witnesses. This number, M127, was the largest known prime from 1876 to 1952, proven by Edouard Lucas.
Comparison with similar methods
| Method | Complexity | Typical use |
|---|---|---|
| Trial Division | O(sqrt(n)) | Small numbers (< 2^32), deterministic |
| Sieve of Eratosthenes | O(n log log n) | Enumerating all primes up to a limit |
| Miller-Rabin (deterministic) | O(k log^3 n) | Numbers < 3.3 x 10^24, provably correct |
| Miller-Rabin (probabilistic) | O(k log^3 n) | Arbitrarily large numbers, 40 rounds for 2^-80 error |
Limitations or considerations
The Sieve of Eratosthenes tab is capped at 1,000,000 to avoid browser memory issues. A Uint8Array of one million bytes is roughly 1 MB, which is fine, but larger limits cause noticeable UI freezes. The Generate tab handles ranges up to 10,000,000 and first-N up to 100,000 primes. The Miller-Rabin test itself has no practical size limit thanks to BigInt, but very large inputs (thousands of digits) will be slow because BigInt multiplication is O(n^2) in the number of digits. The probabilistic mode with 40 random witnesses gives an error probability below 2^-80, which is sufficient for virtually all applications, but it is not a proof. For formal primality proofs of huge numbers, use a deterministic test like the AKS primality test or an elliptic curve method.
Frequently asked questions
Is the Miller-Rabin result always correct?
For numbers below 3,317,044,064,679,887,385,961,981, the tool uses the first 13 primes as witnesses, which gives a deterministic (proven) result. For larger numbers, it uses 40 random witnesses, giving an error probability below 2^-80. This is more than sufficient for cryptographic purposes.
How does the Sieve of Eratosthenes work?
It creates a boolean array from 0 to your limit, then starting at 2, marks every multiple of each unmarked number as composite. The numbers that remain unmarked are prime. The tool uses a Uint8Array for memory efficiency and stops marking at sqrt(limit), since any composite number has a factor at or below its square root.
Can I test numbers larger than JavaScript's Number.MAX_SAFE_INTEGER?
Yes. The Primality Test and Next Prime tabs use BigInt internally, so you can enter numbers of any size. The tool parses your input as a BigInt string. Very large numbers (thousands of digits) will take longer due to the cost of BigInt arithmetic.
What is the Prime Number Theorem and why does it matter?
The Prime Number Theorem states that the number of primes below n is approximately n / ln(n). This means primes get sparser as numbers grow, but the gap between consecutive primes grows only logarithmically. It guarantees that finding the next prime never requires searching too far.
Why use trial division for small numbers instead of Miller-Rabin?
For numbers below 2^32, trial division up to the square root is fast (at most 65,536 divisions) and gives a guaranteed answer. Miller-Rabin would also work, but trial division is simpler and deterministic for this range.
Conclusion
This prime number generator covers the four most common tasks: enumerating primes, testing primality, finding the next prime, and running the Sieve of Eratosthenes. The Miller-Rabin implementation handles BigInt inputs with deterministic witnesses for numbers under 3.3 x 10^24 and 40 random rounds for anything larger. Everything runs client-side, so your inputs never leave the browser. Use it for RSA key generation, number theory coursework, or verifying prime counts against the Prime Number Theorem.