Swift) 백준 4948번 (베르트랑 공준)

요구능력 : 에라토스테네스의 체를 이해하고 있냐

 

코드설명 : 

문제에서는 0이 입력되면 종료한다고 했으므로 while문을 통해 n이 0일경우 break를 걸었다.

그리고 1의 경우 에라토스테네스의 체로 신경쓸 수 있는 부분이 아닌것 같으므로 따로 처리해줬다.

아래는 에라토스테네스의 체를 이용해서 구해줬다.

배열을 2부터 생성해줘야 2의 배수를 다 없앨 수 있기 때문에 2부터 생성해줬고

마찬가지로 2의배수부터 배수를 쭉 없애줘야 하기 때문에 2의 배수부터 배열을 0을 만들어 줬다고 보면된다.

그리고 범위가 n < ☺️ <= 2n 이기 때문에 여기에 해당하는 소수만 구하기 위해서 범위설정해주고 arr[w]가 0이 아닌게 결국 소수이기 때문에 그 때 갯수를 count로 세준 것이다.

 

후기 : 에라토스테네스의 체를 이해하고 나면 소수관련문제는 매우 순탄한듯싶다.

 

while true {
    var count = 0
    let n = Int(readLine()!)!
    if n == 0 {
        break
    }else if n == 1 {
        print("1")
        continue
    }

    var arr: [Int] = Array(repeating: 1, count: (2 * n) + 1 )
    for i in 2...(2 * n) {
        arr[i] = i
    }
    for j in 2...(2 * n) {
        for k in stride(from: j + j, through: (2 * n), by: j) {
            arr[k] = 0
        }
    }

    for w in (n + 1)...(2 * n) {
        if arr[w] != 0 {
            count += 1
        }
    }
    print("\(count)")
}