[Algorithm] 백준 - 1929번 소수구하기 (Swift) (에라토스테네스의 체)

문제 소개

1929번: 소수 구하기

첫째 줄에 m, n이 주어지면 m이상 n이하의 자연수를 출력하는 문제이다.
 

문제 풀이

2부터 시작해서 배수를 소거해나가는 "에라토스테네스의 체" 알고리즘을 사용했다. 배열을 편하게 index와 숫자를 동일시해서 Array(0...n)으로 배열을 초기화 해주었다. 그리고 어떠한 수의 배수가 된다면 1로 변경하였다.
 
Int(sqrt(Double(n))) + 1 이 부분은 어떤 의미이냐면 2부터 n까지의 모든 숫자의 배수를 하나하나 대조해보는 것이 아니라 100인 경우 10까지만 생각하면 된다는 것이다. 왜냐하면 11의 경우 121부터가 검사할 수있는 최소의 수이기 때문이다. 이전의 22나 44, 55는 2, 4, 5의 배수이기 때문이다. 121부터가 새로운 수이다.

import Foundation

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let (m, n) = (input[0], input[1])

var primeNumber = Array(0...n)

for i in 2...Int(sqrt(Double(n))) {
    if primeNumber[i] != 1 {
        var j = 2
        while i * j <= n {
            primeNumber[i * j] = 1
            j += 1
        }
    }
}

for i in m...n {
    if primeNumber[i] != 1 {
        print(primeNumber[i])
    }
}