Prime Number Generator
Generate all prime numbers up to a given limit using the Sieve of Eratosthenes.
About Prime Number Generator
The Sieve of Eratosthenes is one of the oldest and most efficient algorithms for finding all prime numbers up to a given limit. It works by iteratively marking the multiples of each prime starting from 2. Numbers remaining unmarked after all passes are prime. Its time complexity is O(n log log n), making it practical for limits up to about 10 million in a browser environment.
Formula
Sieve complexity
Time ≈ O(n × log(log(n))); Space = O(n)
- n
- Upper bound
Worked example
With the default values below, Prime Number Generator returns Number of Primes of 25. Change any input above and every figure here is recalculated in your browser.
Inputs used
- Upper Boundaccepts 2–10,000,000
- 100
Results
- Number of Primes
- 25
- Largest Prime
- 97
- Prime List
- 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
Step by step
- 1Algorithm
- 2Range
- 3Primes found= 25
Assumptions and limits
- The result is derived only from the single input listed above. Anything not among them is not part of the calculation.
- In particular, this calculator does not take inflation, tax, fees or charges or compounding frequency into account.
- Figures are rounded for display to whole numbers, so totals built from several rounded parts can differ slightly from the unrounded arithmetic.
How these calculators are built and tested is described on the Methodology page. If a figure looks wrong, please report it.
Frequently Asked Questions
Why is the upper bound limited to 10 million?
The sieve allocates an array of size n. Beyond 10 million entries, memory use and computation time can freeze a browser tab. For larger searches, use a segmented sieve in a native application.
How does the Sieve of Eratosthenes work?
Start with all numbers 2 to n marked as candidates. Take the smallest unmarked number (2), mark all its multiples as composite, then advance to the next unmarked number and repeat. Every number that is never crossed off is prime.