Prime Number Generator

How Does This Prime Number Generator Work?

Finding a large prime is fundamentally a search problem. There is no practical formula that jumps directly to the next prime of an arbitrary size, and primes become less common as numbers grow. This generator therefore creates or selects suitable candidates, eliminates easy composites in batches, and applies a stronger primality test only to the survivors. Each stage is designed to avoid expensive large-integer work whenever a cheaper test can settle the question first.

1. It Chooses the Fastest Path for the Request

• Prime by digit count: Requests from 1 to 20 digits use prevalidated primes and return immediately. Larger requests are sent to background search workers so the page remains responsive.
• Next probable prime after N: Small inputs below 10,000,000 use a lightweight deterministic integer search. Larger values are scanned in strictly ascending order by one background worker.
• Generate Again: The new search begins immediately above the displayed result. This produces a larger prime instead of repeating the same candidate; one worker is used so the ascending search remains well defined.

2. Workers Search Adaptive Blocks of Odd Numbers

For a new digit-count search above 20 digits, every worker starts at an independently selected N-digit odd number. The first digit is nonzero and the last digit is restricted to 1, 3, 7, or 9, avoiding values that are immediately divisible by 2 or 5. From that starting point the worker examines ascending odd values in blocks. Block sizes adapt from 1,024 up to 32,768 candidates, amortizing sieve setup for very large numbers without allowing memory use to grow without a bound.

3. A Segmented Sieve Removes Easy Composites

Each worker builds the 9,592 small primes up to 100,000 once. For every candidate block, a segmented Sieve of Eratosthenes marks values divisible by those primes. Computing one remainder per small prime for the whole block is substantially cheaper than trial-dividing every large candidate separately. More than 90% of odd candidates are normally rejected here, before the stronger primality engine is needed.

4. Survivors Enter the Primality Engine

A sieve survivor is passed to the shared BigInt primality engine with a flag confirming that small-prime division has already been completed. This prevents the engine from repeating the same work. It then selects a test according to the candidate's size:

• Below 10⁸: Division by the precomputed primes up to 10,000 is a complete proof, because any composite in this range must have a factor no larger than its square root.
• From 10⁸ to 2⁶⁴: A deterministic Miller–Rabin test uses fixed, proven base sets. Four bases are sufficient for smaller values in this range, while seven specific bases cover every unsigned 64-bit integer.
• At or above 2⁶⁴: A perfect-square check is followed by the Baillie–PSW test—a strong base-2 Miller–Rabin test plus a strong Lucas test. A passing value is labeled a probable prime because this is not a formal primality certificate, although no composite number is known to pass the combined test.

5. Independent Workers Race to the First Result

Fresh digit-count searches use the browser's reported logical processor count, leave one processor available for the page and other work, and run no more than eight workers. Each worker starts in a different part of the requested digit range. The first worker to find an acceptable prime wins and the others are stopped immediately. Next-prime and Generate Again searches use one worker because their job is to scan upward from a specific value rather than sample independent regions.

Why Not Use One Huge Sieve of Eratosthenes?

A traditional sieve is excellent when the goal is to list every prime below a manageable upper bound. It requires storage proportional to that bound, however. Sieving every integer up to a 100-digit—let alone a 20,000-digit—number is physically impossible. This generator uses the useful part of the sieve idea only on small windows near its current search position, then uses BigInt primality tests that operate directly on each surviving candidate. The hybrid approach provides most of the sieve's filtering benefit without allocating an impossible array.

Why Finding Larger Primes Takes Longer

Two costs grow with the requested size. First, large-integer multiplication and modular arithmetic become more expensive. Second, primes become less dense. The Prime Number Theorem describes this density:

Near x, roughly one integer in ln(x) is prime. Because the workers scan only odd values, an N-digit search expects approximately the following number of screened positions before finding a prime:

This is an average, not a deadline: prime gaps vary, so a result can arrive much earlier or later. The pre-sieve ensures that only a small fraction of those odd positions require a full Miller–Rabin or Baillie–PSW evaluation.

How to Read the Progress Display

The overall progress bar cannot know exactly where the next prime will appear. It uses the Prime Number Theorem estimate and a search window of about three expected prime spacings, which corresponds to a useful roughly 95% heuristic. The displayed percentage is deliberately prevented from moving backward, but it remains an estimate rather than a guaranteed completion time. After the first 10 seconds, Estimated time remaining converts that percentage and the observed elapsed time into a smoothed duration, so it may move up or down as the measured search rate changes.

Each worker also has its own bar for the candidate currently being tested. The primality engine estimates that candidate's work in modular multiplications, so a worker bar can restart when the worker advances to another candidate. The Operations statistic is different: it is cumulative across all workers and never resets during a generation run.

What the Result Does—and Does Not—Guarantee

Results below 2⁶⁴ are deterministic. Larger results are explicitly labeled probable primes, reflecting the Baillie–PSW guarantee described above. Composite candidates are rejected with a definite witness; a large passing candidate is not accompanied by a formal certificate that another program can independently verify as a proof.

Although initial digit-count seeds come from the browser's crypto.getRandomValues, this tool is optimized for finding a result quickly, not for uniform prime sampling, secrecy, or compliance with a cryptographic key generation standard. Its output is displayed openly and should not be used directly as private RSA or signing-key material.

Explore More Prime Number Topics

Dive deeper into the properties and history of prime numbers with our guides:

• Prime Number Checker – Test any number for primality with real-time proofs.
• How to Check if a Number is Prime – From trial division to Baillie–PSW and AKS.
• What Are Prime Numbers? – Foundational concepts and the Fundamental Theorem of Arithmetic.
• The Sieve of Eratosthenes – The classical ancient algorithm for generating lists of primes.
• Different Types of Primes – Mersenne, Fermat, Twin, and Sophie Germain primes.
• A Very Large Prime Number – Exploring massive record-setting primes.