Skip to main content

Sieve of Eratosthenes - Solutions

Approach: Sieve of Eratosthenes Algorithm​

Description​

The Sieve of Eratosthenes is an efficient algorithm for finding all prime numbers up to a specified integer n. It works by iteratively marking the multiples of each prime number starting from 2. The numbers that remain unmarked after all multiples of known primes have been marked are the prime numbers.

Implementation​

func sieveOfEratosthenes(upTo n: Int) -> [Int] {
    guard n >= 2 else { return [] }
    
    var isPrime = [Bool](repeating: true, count: n + 1)
    isPrime[0] = false
    isPrime[1] = false
    
    for number in 2...Int(Double(n).squareRoot()) {
        if isPrime[number] {
            for multiple in stride(from: number * number, through: n, by: number) {
                isPrime[multiple] = false
            }
        }
    }
    
    return (2...n).compactMap { isPrime[$0] ? $0 : nil }
}

Pros​

  • Very efficient for finding all prime numbers up to a large number n.
  • Time complexity is O(n log log n), which is much better than checking each number individually for primality.

Cons​

  • Requires O(n) space to store the boolean array isPrime.
  • Not suitable for extremely large values of n due to space constraints.

Optimizations and Variations​

Optimization 1: Start Marking from number * number​

Instead of marking multiples starting from 2 * number, we start from number * number because all smaller multiples will have already been marked by smaller primes. This reduces the number of operations significantly.

Implementation​

for number in 2...Int(Double(n).squareRoot()) {
    if isPrime[number] {
        for multiple in stride(from: number * number, through: n, by: number) {
            isPrime[multiple] = false
        }
    }
}

Optimization 2: Using a Bit Array​

For very large values of n, we can use a bit array instead of a boolean array to save space. Each bit in the array represents whether a number is prime.

Discussion: Parallelizing the Sieve​

The Sieve of Eratosthenes can be parallelized to run on multiple cores or even distributed systems. Each core can handle marking multiples of different prime numbers independently.

Edge Cases​

  • If n is less than 2, the function returns an empty array since there are no prime numbers less than 2.
  • Handling very large values of n requires careful memory management to avoid running out of memory.

Conclusion​

The Sieve of Eratosthenes is an efficient and well-known algorithm for finding prime numbers up to a given limit. With optimizations like starting from number * number and using bit arrays, it can handle large values efficiently. Understanding and implementing this algorithm provides a strong foundation for working with prime numbers and understanding algorithmic efficiency.