[알고리즘] 에스토스테네스의 체 (소수 판별 알고리즘)

에스토스테네스의 체?

 

소수를 찾기 위한 고전적인 알고리즘으로

일반적으로 수를 하나씩 체크하며 소수를 판별하는 것은 비효율적이기 때문에 에스토스테네스의 체 알고리즘을 사용하면 좋다.

 

원리

 

[1 ... 50]까지 존재한다고 가정하였을 때

동일한 크기의 Bool 타입의 true로 가득 찬 배열을 생성한다.

 

[1 ... 50]

* 지워준다 == false로 변환

여기서 2부터 배수를 지워준다.

 

이 후 다음 3의 배수를 지워준다.

 

4의 배수는 이미 2의 배수에서 지워졌다

이렇게 계속 배수를 지워주는데, 언제까지 지워주는지가 중요할 것이다.

---

50의 경우 제곱근이 7.0****이 나오게 된다.

 

이때 50보다 작은 수 중 소수가 아닌(m)은 m = a * b가 된다. (a <= b)

이때 a는 무조건 50의 제곱근 7.0*****보다 작게 된다.

 

이는 7.0****보다 작은 정수의 배수를 모두 지워주게 되면, 소수가 아닌 m이 모두 지워지게 된다.

다만 첫 정수는 소수일 가능성이 있기 때문에, stride에서 from이 number 부터가 아닌 number의 제곱부터 진행하게 된다.

 

import Foundation
 
func sieveOfEratosthenes(upTo limit: Int) -> [Int] {
    guard limit >= 2 else { return [] }  // 2보다 작은 경우 빈 배열 반환
 
    // 0과 1은 소수가 아니므로 false로 설정한다.
    var isPrime = [Bool](repeating: true, count: limit + 1)
    isPrime[0] = false
    isPrime[1] = false
 
    // 2부터 시작하여 각 숫자의 배수를 지운다.
    let sqrtLimit = Int(sqrt(Double(limit)))
    
    for number in 2...sqrtLimit {
        if isPrime[number] {
            // 현재 숫자의 배수를 지운다.
            for multiple in stride(from: number * number, through: limit, by: number) {
                isPrime[multiple] = false
            }
        }
    }
 
    // 소수인 숫자만 필터링하여 반환한다.
    return isPrime.enumerated()
        .compactMap { return $1 ? $0 : nil }
}
 
// 사용 예
let limit = 50
let primes = sieveOfEratosthenes(upTo: limit)
print("Primes up to \(limit): \(primes)")