Sieve of Eratosthenes

The Sieve of Eratosthenes is one of the most efficient ways to find all prime numbers up to a given limit n. This ancient algorithm, attributed to Eratosthenes of Cyrene (276-194 BC), remains relevant today due to its simplicity and efficiency.

Mathematical Definition

Let's define the Sieve of Eratosthenes formally:

Given a number n, the algorithm finds all prime numbers less than or equal to n by:

1. Creating a list of all integers from 2 to n
2. Starting with p = 2 (the smallest prime number)
3. Marking all multiples of p (excluding p itself) as composite
4. Finding the next unmarked number and repeating step 3
5. Continuing until p² > n

The mathematical foundation relies on the fact that any composite number must have a prime factor less than or equal to its square root.

Time and Space Complexity

The time complexity of the Sieve of Eratosthenes is:

This comes from the fact that each number is crossed out approximately times. The space complexity is , as we need to maintain a boolean array of size .

JavaScript Implementation

Here's an efficient implementation of the Sieve of Eratosthenes in JavaScript:

code.js
1function sieveOfEratosthenes(n) {
2    // Create array of size n+1 and fill with true
3    const isPrime = new Array(n + 1).fill(true);
4    
5    // 0 and 1 are not prime
6    isPrime[0] = isPrime[1] = false;
7    
8    // Start with 2, the first prime number
9    for (let i = 2; i * i <= n; i++) {
10        // If i is prime, mark all its multiples as non-prime
11        if (isPrime[i]) {
12            for (let j = i * i; j <= n; j += i) {
13                isPrime[j] = false;
14            }
15        }
16    }
17    
18    // Collect all prime numbers
19    const primes = [];
20    for (let i = 2; i <= n; i++) {
21        if (isPrime[i]) {
22            primes.push(i);
23        }
24    }
25    
26    return primes;
27}
28
29// Example usage:
30console.log(sieveOfEratosthenes(30));
31// Output: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Optimizations

Several optimizations can be applied to the basic sieve:

1. Memory Optimization: We can use a bit array instead of a boolean array to reduce memory usage by a factor of 8.
2. Computational Optimization: We can skip even numbers after 2, reducing the work by half.

Here's an optimized version:

code.js
1function optimizedSieve(n) {
2    if (n < 2) return [];
3    
4    // Only store odd numbers to save memory
5    const isPrime = new Array(Math.floor(n/2)).fill(true);
6    
7    // Handle multiples of odd numbers
8    for (let i = 3; i * i <= n; i += 2) {
9        if (isPrime[Math.floor(i/2)]) {
10            for (let j = i * i; j <= n; j += 2 * i) {
11                isPrime[Math.floor(j/2)] = false;
12            }
13        }
14    }
15    
16    // Collect primes
17    const primes = [2];
18    for (let i = 3; i <= n; i += 2) {
19        if (isPrime[Math.floor(i/2)]) {
20            primes.push(i);
21        }
22    }
23    
24    return primes;
25}

Applications

The Sieve of Eratosthenes has several practical applications:

1. Finding prime numbers for cryptographic algorithms
2. Number theory research
3. Factorization algorithms
4. Educational purposes to understand prime numbers

Limitations

While efficient for smaller ranges, the Sieve of Eratosthenes has some limitations:

1. Memory requirements grow linearly with n
2. Not suitable for testing individual large numbers
3. Cannot efficiently find primes in a range [a,b] where a is large

For testing individual large numbers, other algorithms like Miller-Rabin or Fermat tests are more appropriate.