Sieve of Eratosthenes
Ancient and highly efficient algorithm to find all prime numbers up to a given limit n. Invented by Greek mathematician Eratosthenes of Cyrene (276-194 BC), this sieve method systematically eliminates multiples of primes, leaving only primes in the array. With O(n log log n) time complexity, it remains one of the most practical algorithms for generating large lists of primes, vastly superior to trial division which runs in O(n² / log n) time.
Visualization
Interactive visualization for Sieve of Eratosthenes
Sieve of Eratosthenes Visualization
Ancient algorithm to find all primes up to n in O(n log log n) time
Time Complexity: O(n log log n)
Space Complexity: O(n)
How it works:
- Mark all numbers from 2 to n as potential primes
- For each prime p starting from 2
- Mark all multiples of p (starting from p²) as composite
- Continue until p² > n
- Remaining marked numbers are primes
Interactive visualization with step-by-step execution
Implementation
1function sieveOfEratosthenes(n: number): number[] {
2 const isPrime = new Array(n + 1).fill(true);
3 isPrime[0] = isPrime[1] = false;
4
5 for (let i = 2; i * i <= n; i++) {
6 if (isPrime[i]) {
7 for (let j = i * i; j <= n; j += i) {
8 isPrime[j] = false;
9 }
10 }
11 }
12
13 const primes: number[] = [];
14 for (let i = 2; i <= n; i++) {
15 if (isPrime[i]) primes.push(i);
16 }
17
18 return primes;
19}Deep Dive
Theoretical Foundation
The sieve works by iteratively marking multiples of each prime as composite. Starting with 2, mark all multiples of 2 (except 2 itself). Then find the next unmarked number (which must be prime), and mark all its multiples. The key insight is that we only need to check up to √n, because if n is composite, it must have a factor ≤ √n. The time complexity of O(n log log n) comes from the harmonic series of primes: n/2 + n/3 + n/5 + n/7 + ... ≈ n log log n.
Complexity
Time
O(n log log n)
O(n log log n)
O(n log log n)
Space
O(n)
Applications
Industry Use
RSA cryptography (generating large prime pairs)
Hash table prime sizing
Number theory research
Goldbach's conjecture verification
Twin prime finding
Cryptographic key generation
Prime number distribution studies
Mathematical olympiad problem solving
Pollard's rho factorization preprocessing
Use Cases
Related Algorithms
GCD (Euclidean Algorithm)
Compute the Greatest Common Divisor (GCD) of two integers using the Euclidean algorithm. Dating back to around 300 BC and appearing in Euclid's Elements, it's one of the oldest algorithms still in common use. The algorithm is based on the principle that GCD(a,b) = GCD(b, a mod b) and is remarkably efficient with O(log min(a,b)) time complexity. The GCD is the largest positive integer that divides both numbers without remainder.
LCM (Least Common Multiple)
Calculate the Least Common Multiple (LCM) of two integers - the smallest positive integer that is divisible by both numbers. The LCM is intimately related to the GCD through the formula: LCM(a,b) = |a×b| / GCD(a,b). This relationship allows us to compute LCM efficiently using the Euclidean algorithm for GCD, achieving O(log min(a,b)) time complexity instead of naive factorization methods.
Prime Factorization
Decompose a positive integer into its unique prime factor representation. Every integer greater than 1 can be expressed as a product of prime numbers in exactly one way (Fundamental Theorem of Arithmetic). This algorithm uses trial division optimized to check only up to √n, as any composite number must have a prime factor ≤ √n. Returns a map of prime factors to their powers, e.g., 360 = 2³ × 3² × 5¹.
Modular Exponentiation (Fast Power with Modulo)
Efficiently compute (base^exponent) mod m without overflow, crucial for cryptographic operations. Computing large powers like 2^100 mod 1000000007 is impossible with naive exponentiation due to integer overflow, but modular exponentiation achieves this in O(log exponent) time using the binary representation of the exponent. This algorithm is the foundation of RSA encryption, Diffie-Hellman key exchange, and many cryptographic protocols.