Swift - 에라토스테네스의 체(sieve of Eratosthenes) for 소수 판별

📎 간단한 소수 판별법

• 소수 판별에는 여러가지 방법이 있습니다. 사실 가장 간단한 방법은 Brute Force로 2보다 크고 소수 판별의 대상인 수보다 1 작은 모든 수를 탐색하며 나누어 떨어지는지 확인하는 것입니다. 예시를 통해 설명하면 아래와 같습니다.

  func isPrime(checkNumber: Int) -> Bool {
      let criterion = checkNumber - 1
      for i in 2...criterion {
          if checkNumber % i == 0 {
              return false
          }
      }
      return true
  }

  
  

  여기서 한단계 더 나아간다면 모든 수를 체크하는 것이 아니라 제곱근까지만 탐색해도 됩니다. 왜냐하면 소수가 아닌 수는 인수가 존재하고, 인수는 곱의 쌍으로 존재하기 때문에 제곱근 이상에서 나눌 수 있는 수가 있다면 제곱근 이하에 반드시 나눠지는 수가 존재해야하기 때문입니다. 예를 들어 16의 인수의 경우 8이 있을 수 있는데 이 경우는

  2 * 8 = 16

  으로 16의 제곱근인 4보다 작은 2가 반드시 존재해야합니다. 즉, 소수 판별을 위해 2를 찾았다면 굳이 8까지 찾을 필요가 없는 것이죠. 그래서 위의 식은 O(N)이지만 위의 개념을 통해 연산을 N의 제곱근으로 줄일 수 있습니다.

  func isPrime(checkNumber: Int) -> Bool {
      let criterion = Int(Double(checkNumber).squareRoot()) // 기준점 변경
      for i in 2...criterion {
          if checkNumber % i == 0 {
              return false
          }
      }
      return true
  }

  
  

  하지만 이것 역시 가장 완벽한 탐색법이라고 볼 수는 없습니다. 숫자가 커질 수록 연산의 개수가 급격하게 늘어나기 때문입니다. 그래서 저는 파이썬으로 알고리즘을 구현할 때 소수 판별에서 항상 에라토스테네스의 체 라는 개념을 사용했습니다.

📈 에라토스테네스의 체(sieve of Eratosthenes)

• 에라토스테네스의 체(sieve of Eratosthenes)는 1보다 크고 특정 수 이하인 구간에서 존재하는 소수를 찾는 방식입니다. 더 자세한 내용은 아래 출처의 위키백과에서 확인할 수 있습니다.
  
• 간략하게 설명하자면, 2부터 시작해서 소수들의 배수를 해당 구간에서 제거하는 방식으로 작업하여 남는 모든 수가 소수가 됩니다. 예를 들어 120 이하의 수 중 소수인 것을 판별한다면 ... 10의 제곱근, 11의 제곱근, ... , 100의 제곱근, 101의 제곱근, ... , 120의 제곱근을 모두 더한 것 만큼의 연산이 필요합니다. 하지만 120은 11의 제곱인 121보다 작기 때문에 2, 3, 5, 7, 11의 배수만 120 이하에서 제거해주면 됩니다. 즉, 필요한 연산이 줄어들게 됩니다. 이제 Swift로 에라토스테네스의 체를 구현하는 방법을 알아보겠습니다.

🙋‍♂️ 내가 처음 생각한 해결 방법

• 사실 파이썬의 경우 리스트에서 요소를 추가하고 제거하는 작업이 매우 쉽기 때문에 소수가 아닌 합성수를 제거하는 작업을 직접 구현하는 리스트를 구현하는게 어렵지 않았습니다. 예를 들면

  [1, 2, 3, 4, 5, 6, 7]

  이 있다면 여기서 먼저 1을 제거한 후 2의 배수를 제거할 때

  [3, 5, 7]

  로 요소를 remove 하는 것이 어렵지 않았습니다. 하지만 리스트의 요소를 매번 변화시켜 사이즈의 변화를 주는 것은 그렇게 빠른 연산이 아니었습니다. append나 pop 작업은 코스트가 많이 드는 작업입니다. 마찬가지로 Swift에서 역시 이 방법은 번거로운데다가 속도 측면에서도 유리하다고 볼 수 없기 때문에 Bool 값을 갖는 배열을 생성하여 연산합니다.

💻 풀이한 코드

func makeCompositeNumberFalse(flags: inout [Bool], prime: Int) {
    for i in stride(from: prime * prime, to: flags.count, by: prime) {
        flags[i] = false
    }
}

func nextPrime(cache: inout [Bool], prime: Int) -> Int {
    var next = prime + 1
    while next < cache.count, !cache[next] {
        next += 1
    }
    return next
}

func sieveOfEratosthenes(n: Int) -> [Bool] {
    var cache = Array(repeating: true, count: n + 1) // index를 맞추기 위해 n + 1

    cache[0] = false // 0은 소수가 아님
    cache[1] = false // 1은 소수가 아님

    var prime = 2 // 소수 판별 시작 기준

    while prime <= Int(sqrt(Double(n))) { // 제곱근 이상의 수는 prime * prime 하는 순간 기준 이탈이므로 제곱근 이하만 탐색해도 됨
        makeCompositeNumberFalse(flags: &cache, prime: prime) // 소수의 배수들을 제거
        prime = nextPrime(cache: &cache, prime: prime) // 다음 소수로 기준 변경
    }

    return cache // index의 값이 true인 경우 소수
}

📝 해결 과정에서 만난 문제, 고민들

• python의 경우 sqrt가 Math를 import해야 사용할 수 있었지만 Swift에서는 Double을 파라미터로 받는 메소드로 존재하여 바로 sqrt로 사용 가능합니다.
• stride(from:to:by:)는 반복을 할 때 1씩 증가하는 것이 아니라 by 만큼의 차이를 점프하며 증가할 때 사용합니다.

Ref: 에라토스테네스의 체 위키백과