Generate prime numbers instantly using the classical Sieve of Eratosthenes. Choose between range-based generation (up to 10 million) or first N primes. View prime list, count, sum, and download results as text.
The Sieve of Eratosthenes is one of the most efficient classical algorithms for generating all primes up to a given limit. Attributed to the Greek mathematician Eratosthenes of Cyrene (c. 276–194 BCE), it works by iteratively marking multiples of each prime starting from 2. The remaining unmarked numbers are prime. This algorithm runs in \( O(n \log \log n) \) time and uses \( O(n) \) memory, making it optimal for ranges up to tens of millions in modern browsers.
For a given limit \( N \), the Sieve of Eratosthenes eliminates composites by iterating \( p = 2,3,5,\dots \) and marking \( p^2, p^2 + p, p^2 + 2p, \dots \) as composite.
The time complexity of \( O(n \log \log n) \) and space complexity of \( O(n) \) make the Sieve of Eratosthenes highly efficient for generating all primes up to moderate bounds (typically ≤ 10⁸ in optimized implementations). The \( \log \log n \) factor emerges from the harmonic series of primes. Our browser implementation includes standard optimizations: skipping even numbers (a simple form of wheel factorization), starting marking from \( p^2 \), and using typed arrays for memory efficiency.
Our implementation uses a typed Uint8Array to store boolean flags (0/1) for primality up to the specified limit. For range mode, the classical sieve marks composites starting from \( p^2 \) to avoid redundant work. For count mode (first N primes), the tool dynamically estimates an upper bound using the prime number theorem: the nth prime is roughly \( n \ln n \). It then runs a segmented approach or simply extends the sieve until enough primes are found. The result is a sorted list of primes, accompanied by statistics: count, largest prime, sum, and density \( \pi(N)/N \).
Performance optimizations include: skipping even numbers after 2 (a basic wheel optimization), using bit-level operations where feasible, and limiting maximum range to 10 million to prevent browser unresponsiveness. For count mode, we cap at 100,000 primes (largest ~1,299,709) which is processed within seconds. More advanced wheel factorizations (mod 30, 210) are possible but increase code complexity with diminishing returns for typical educational use.
The Prime Number Theorem (PNT) describes the asymptotic density of primes: the number of primes less than or equal to \( x \) is approximately \( \frac{x}{\ln x} \). Our generator displays the empirical density \( \pi(N)/N \), allowing you to verify the PNT for different ranges. For example, \( \pi(10^6) = 78,498 \) while \( 10^6 / \ln(10^6) \approx 72,382 \). The ratio approaches 1 as N increases.
The PNT gives the first-order approximation \( \pi(x) \sim \frac{x}{\ln x} \). More accurate approximations include \( \frac{x}{\ln x - 1} \) and the logarithmic integral \( \operatorname{Li}(x) = \int_2^x \frac{dt}{\ln t} \). The error term in the PNT remains an active research area connected to the Riemann Hypothesis.
| Range (N) | π(N) (primes ≤ N) | Approx. N/ln(N) | Density π(N)/N |
|---|---|---|---|
| 102 | 25 | 21.7 | 0.250 |
| 103 | 168 | 144.8 | 0.168 |
| 104 | 1,229 | 1,085.7 | 0.1229 |
| 105 | 9,592 | 8,685.9 | 0.0959 |
| 106 | 78,498 | 72,382.4 | 0.0785 |
Data sourced from OEIS sequence A006880 and prime number theorem approximations.
Generate primes up to 10,000 and count how many twin prime pairs (p, p+2) exist. The tool's output can be analyzed manually: for N=10,000 there are 205 twin prime pairs, with the largest being (9929, 9931). This real-time exploration helps students appreciate unsolved problems in number theory. The Twin Prime Conjecture states there are infinitely many such pairs – though unproven, computational evidence strongly supports it. Use this tool to explore prime gaps and twin prime distribution patterns.