백준 - 소수 구하기 (1929)

import Foundation

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

var array = Array(0...N)
var answer = ""

(array[0], array[1]) = (0, 0)

for i in stride(from: 2, through: Int(Double(N).squareRoot()), by: 1) {
    let now = array[i]
    if now == 0 {
        continue
    }
    for j in stride(from: i+i, to: array.count, by: i) {
        array[j] = 0
    }
}

for i in M...N {
    if array[i] != 0 {
        answer += "\(array[i])\n"
    }
}

print(answer)

• N의 최대값이 1,000,000이기 때문에 에라토스테네스의 채를 사용하여 문제를 풀어야 한다.
• 크기가 N+1인 배열을 선언한 후 2부터 N의 제곱근까지만 값을 탐색하며 현재 탐색 중인 값의 배수들을 모두 지운다.

소수 구하는 문제는 원래 몇 번 풀어봤지만 이 문제는 유독 잔실수가 많았다. 특히 Range에 관한 오류가 엄청 많았다…

1. 배열에서 0이랑 1번째 값을 미리 0으로 만들려고 var array = [0, 0] + Array(2...N) 이라고 선언했었는데, N이 1인 경우에는 범위를 올바르게 계산할 수가 없다. (굳이 저딴 식으로 선언할 필요가 없는데… 바보인가 진짜)
2. N의 제곱근까지만 탐색하기 위해 처음에는 for i in 2...Int(Double(N).squareRoot()) 라고 코드를 짰는데, 여기서도 N의 제곱근이 2보다 작은 경우에는 범위를 계산할 수 없어 에러가 발생한다.

→ 입력값의 범위를 꼭꼭!! 잘 확인하고 필요한 경우에는 stride 메소드를 사용하는 방법도 생각해보자.

1. 현재 보고 있는 값의 배수만 탐색해야 하는데 아무 생각 없이 안쪽 for문을 for j in i+1..<array.count 라고 썼다가 시간초과가 되었다..ㅎㅎ 제발 꼼꼼하게 좀 풀자!!