에라토스테네스의 체 알고리즘

소수의 정의는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수입니다.
저한테 누가 소수를 판별하는 코드를 짜보라고 하면 아래와 같이 짤 것 같아요.

func isPrimeNumber(n: Int) -> Bool {
    guard n > 1 else { return false }
    for i in 2..<n {
        if n % i == 0 {
            return false
        }
    }
    return true
}

1 초과가 아니면 거짓을 리턴해주고 1을 초과해야지만 루프를 돌게 됩니다.
루프를 돌면서 나머지가 0이면 나누어 떨어진다는 의미니 거짓을 리턴해주며, 다 돌았을 때는 참을 리턴해줍니다.

오늘 책을 보다가 에라토스테네스의 체에 대해서 알게 되었고 정리해보려 합니다.
에라토스테네스의 체는 소수 목록을 만드는 효율적인 방법이라고 합니다.
이 알고리즘은 소수가 아닌 수들은 반드시 다른 소수로 나누어진다는 사실에 기반해서 동작하게 됩니다.

책에서는 자바로 적혀있길래..
아래는 스위프트로 짜 본 에라토스테네스의 체 코드입니다.

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

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

func sieveOfEratosthenes(max: Int) -> [Bool] {
    var flags = Array(repeating: true, count: max + 1)
    
    flags[0] = false
    flags[1] = false
    
    var prime = 2
    
    while prime <= Int(sqrt(Double(max))) {
        crossOff(flags: &flags, prime: prime)
        prime = getNextPrime(flags: &flags, prime: prime)
    }
    
    return flags
}

먼저 sieveOfEratosthenes(max: Int) 함수를 보겠습니다.
flags라는 배열을 만들어 줍니다. 
크기는 max + 1이고 true로 초기화를 해줍니다.

다음 flags[0], flags[1]은 false로 해줍니다.
0과 1은 소수가 아니기 때문입니다.

prime이라는 변수에 2를 넣어주고 while문을 돌립니다.
맨 위에 제가 구현했던 코드는 n미만까지 돌려주지만, 제곱근 까지만 돌려도 되기 때문에 제곱근까지만 돌려줍니다. 

crossOff라는 함수에 flags레퍼런스를 넣어주고 prime값을 넣어줍니다.
crossOff함수는 2가 만약에 들어오면 2의 제곱 4부터 stride로 2 간격만큼 증가시키면서 false로 만들어줍니다.
이렇게 하면 2의 배수가 모두 false처리가 됩니다.
3을 넣어주면 3의 제곱부터 3 간격만큼 증가시키면서 false로 만들어주기 때문에 3의 배수도 모두 false처리가 됩니다.

getNextPrime함수에도 flags레퍼런스를 넣어주고 prime값을 넣어줍니다.
다음 소수를 찾아주는 작업을 합니다.
아직 flags에서 값이 flase인 수 중 가장 작은 소수를 찾는 것입니다.

이렇게 하다 보면 2에서 max까지의 구간 내에 있는 모든 소수들의 리스트가 만들어집니다.

 

추가로 아래는 10을 넣었을 때 과정을 그려보았습니다.
(글씨를 못써서.. 보기 어렵겠지만 봐주세요 주륵 ㅠ)

resource: cracking the code