에라토스테네스의 체

1. 문제

• 특정 숫자가 소수인지 아닌지 판별하는것이 아닌,
• 2부터 주어진 수까지 범위 내의 모든 소수를 찾는 알고리즘인 에라토스테네스의 체를 구현

2. 문제 설계

• 1인 소수가 아니므로, 배열에 1번째 원소에는 0을 저장하고 2부터 주어진 수까지 각 수를 배열에 그에 대응하는 위치에 원소를 저장함
• 가장 작은 소수인 2부터 그의 배수들을 배열에서 모두 0으로 지워나가면 소수만 남게됨
• 따라서, 주어진 수가 N이라면 O(N log N)에 특정 범위내의 모든 소수를 찾을 수 있음
• 특정 수가 소수인지 아닌지를 판별하는 문제에서는 제곱근 까지 나누어보는 것이 효율적이고,
• 특정 범위 내의 모든 소수를 찾을 때는 에라토스테네스의 체를 활용하는 것이 효율적임

3. 전체 코드

//MARK: - 에라토스테네스의 체

//MARK: - Framework
import Foundation

//MARK: - Variable
var candidates: [Int] = []

//MARK: - Function
func getEratos(_ number: Int) -> Void {
    for i in stride(from: 2, through: number, by: 1) {
        for j in stride(from: i * 2, through: number, by: i) {
            if candidates[j] == 0 {
                continue
            }
            candidates[j] = 0
        }
    }
}

func solution() -> Void {
    //MARK: - Input
    guard let N: Int = Int(readLine() ?? "0") else { return }
    candidates = Array(repeating: 0, count: N + 10)

    for i in stride(from: 2, through: N, by: 1) {
        candidates[i] = i
    }

    //MARK: - Process
    getEratos(N)

    //MARK: - Output
    for i in 1...N {
        if candidates[i] == 0 {
            continue
        }

        print("\(candidates[i]) ", terminator: "")
    }
}
solution()

전체코드는 여기에서 확인할 수 있습니다.