Sieve of Eratosthenes for Factorization

The Sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to a given limit. When adapted for factorization, it provides an efficient way to find prime factors by first generating a list of primes and then using them to factorize numbers. This approach is particularly effective when multiple numbers need to be factorized, as the prime list can be reused.

History

Eratosthenes of Cyrene, a Greek mathematician, was born around 276 BC. He is known for his work in geometry, geography, and astronomy. The Sieve of Eratosthenes, an algorithm for finding all prime numbers up to a given limit, is one of his most famous contributions to mathematics.

Algorithm Overview

Assume that all numbers are prime. Starting with the number , mark all its multiples as non-prime. Then, move to the next number and repeat the process.

The time complexity of the Sieve of Eratosthenes is for generating primes up to . The factorization phase has a time complexity of , where is the prime-counting function. The space complexity is for storing the sieve array.

Implementation

code.js
1function sieveOfEratosthenes(limit) {
2    const sieve = new Array(limit + 1).fill(true);
3    sieve[0] = sieve[1] = false;
4    
5    for (let i = 2 ; i * i <= limit ; i++) {
6        if (sieve[i]) {
7            for (let j = i * i ; j <= limit ; j += i) {
8                sieve[j] = false;
9            }
10        }
11    }
12    
13    return sieve;
14}
15
16function factorizeWithSieve(n, sieve) {
17    const factors = [];
18    const limit = Math.min(n, sieve.length - 1);
19    
20    for (let i = 2; i <= limit; i++) {
21        if (sieve[i]) {
22            while (n % i === 0) {
23                factors.push(i);
24                n = n / i;
25            }
26        }
27    }
28    
29    if (n > 1) {
30        factors.push(n);
31    }
32    
33    return factors;
34}
35
36// Example usage
37function factorizeNumber(n) {
38    const limit = Math.ceil(Math.sqrt(n));
39    const sieve = sieveOfEratosthenes(limit);
40    return factorizeWithSieve(n, sieve);
41}

Example Usage

Let's factorize the number 120:

code.js
1const result = factorizeNumber(120);
2console.log(result); // [2, 2, 2, 3, 5]

This means that .

Optimization Techniques

One optimization technique is to use a bit array instead of a boolean array, which reduces memory usage significantly.

code.js
1function sieveOfEratosthenes(limit) {
2    // Initialize the sieve with all multiples of 2 marked as non-prime, and
3    // the initial byte with the first prime numbers
4    const sieve = new UInt8Array(Math.ceil(limit / 8)).fill(0b01010101)
5    sieve[0] = 0b00110101
6    //           01234567
7
8    // Special case to handle multiples of three five and seven, which could involve more than
9    // one bit change per byte
10    const threeMask = [ 0b10110110, 0b11011011, 0b01101101 ]
11    let threeIndex = 0
12    for (let i = 1 ; i <= sieve.length ; i++) {
13        sieve[i] &= threeMask[threeIndex]
14        threeIndex = (threeIndex + 1) % 3
15    }
16
17    const fiveMask = [ 0b11011110, 0b11110111, 0b10111101, 0b11101111, 0b01111011 ]
18    let fiveIndex = 0
19    for (let i = 1 ; i <= sieve.length ; i++) {
20        sieve[i] &= fiveMask[fiveIndex]
21        fiveIndex = (fiveIndex + 1) % 5
22    }
23
24    const sevenMask = [ 0b11111101, 0b11111011, 0b11110111, 0b11101111, 0b11011111, 0b10111111, 0b01111111 ]
25    let sevenIndex = 0
26    for (let i = 1 ; i <= sieve.length ; i++) {
27        sieve[i] &= sevenMask[sevenIndex]
28        sevenIndex = (sevenIndex + 1) % 7
29    }
30
31    // Now all multiples of 2, 3 and 5 are marked as non-prime, and the sieve is ready
32    // to be further processed for multiples of 7 onwards
33    for (let byte = 1 ; byte < sieve.length ; byte++) {
34        // Binary 1 in left side of the byte
35        const mask = 128
36
37        for (let bit = initialBit ; bit < 8 ; bit++) {
38            const isPrime = sieve[byte] & mask
39            const index = byte * 8 + bit
40
41            if (isPrime) {
42                for (let i = index * index ; i <= limit ; i += index) {
43                    sieve[Math.floor(i / 8)] &= ~(1 << (i % 8))
44                }
45            }
46
47            // Shift the mask to the next bit
48            mask >>= 1
49        }
50
51        initialBit = 0
52    }
53
54    return sieve
55}

Another technique is implementing segmented sieving, which is particularly beneficial for handling very large numbers. Additionally, wheel factorization can be employed to skip multiples of small primes, thereby improving efficiency. Lastly, parallel processing can be utilized to handle large ranges more effectively, distributing the workload across multiple processors to speed up the computation.

Limitations

The primary limitations of this approach include the significant memory requirements needed to store the sieve array, its inefficiency when dealing with single large numbers, and the constraints imposed by the maximum array size in JavaScript.

Applications

The Sieve of Eratosthenes is particularly useful in batch processing scenarios where multiple numbers require factorization, allowing for efficient computation by leveraging precomputed prime numbers.

In educational settings, this method serves as an excellent demonstration of prime factorization, providing a clear and systematic approach to understanding how composite numbers can be broken down into their prime components.

Furthermore, in the realm of cryptography, where the security of many systems relies on the difficulty of factorizing large numbers, the Sieve of Eratosthenes offers a foundational technique for performing multiple factorizations efficiently. Additionally, it plays a significant role in number theory research and analysis, where understanding the prime structure of numbers is crucial for advancing theoretical insights and applications.