Prime Number Generator
Generate all prime numbers up to a given limit using the Sieve of Eratosthenes.
Inputs
Find all primes ≤ this value (max 10,000,000).
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
Algorithm
Sieve of Eratosthenes
Range
2 to 100
Primes found
= 25
How it works
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
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.