[백준 스위프트] 15965번 K번째 소수

아이디어

서브 테스트가 존재하는 문제이며 이를 통해 효율성과 관련 있는 문제라는 것을 알 수 있다. 이제까지 소수를 구하던 방법으로 이중 for문을 통하여 반복해가며 제곱근에 닿을 때까지 연산을 거듭하는 방식으로 풀려고 했으나 실패했다. 다음으로 찾아낸 방식은 에라토스테네스의 체이다. 넉넉하게 천만까지 소수를 판별하도록 하였다. 

에라토스테네스의 체에 대해 짧게 서술하면 쉽게 구현이 가능하면서도 충분히 빠른 방법이다.

1. 원하는 숫자까지 배열로 세팅을 완료하고 애매한 숫자인 1을 제거한다. (여기서 제거라는 것은 배열에서는 0이나 false로 값을 변경하면 된다)

2. 다음으로 2와 3의 배수를 제거하되 자기 자신은 그대로 둔다.

3. 이와 같이 5의 배수, 7의 배수, 그 다음도 지워나간다. 이미 지워진 수가 충분히 있기 때문에 많은 경우를 고려하지 않아도 된다.  

 

해답

let k = Int(readLine()!)!
var num = 10_000_000
var numArray = Array(repeating: 0, count: num + 1)
var cnt = 0
if k == 1 {
    print("1")
}

for i in 2...num {
    numArray[i] = i
    // 여기서 i가 아니라 뭘로 하든 상관 없다. 핵심은 마크를 하냐 마냐이다.
}

for i in 2...num {
    if numArray[i] == 0 {
        continue
    }
    // stride는 파이썬의 range와 유사하게 작동하는 함수이다. 아래의 경우 i의 2배인 수부터 i만큼 증가시키며 num까지 반복하며 연산을 하는 것을 의미한다. 
    // i+i부터 시작하는 이유는 자기 자신은 남겨두는 의미이다.
    for j in stride(from: i+i, through: num, by: i) {
        numArray[j] = 0;
    }
}

for i in 2...num {
    if numArray[i] != 0 {
        cnt += 1
    }
    if cnt == k {
        print(i)
        break
    }
}