무작정 for문을 돌리게 되면 시간초과가 날 것 같았다.
그래서 에라토스테네스의체를 이용하여 문제를 풀었다.
에라토스테네스의 체에 대한 이해 먼저 해야하는데
2. 소수 구하기 - 에라토스테네스의 체
# 소수 : 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수이다. # 코딩 소수인지 검사하는 함수(isPrime)를 만든다. 1부터 100 사이의 소수를 구하는 ...
wikidocs.net
위 링크를 참고하면 좋을 것 같다.
리스트를 하나 생성한다.
그리고 2부터 시작해서
2의 배수는 모두 지우고
3의 배수 모두 지우고
5의 배수 모두 지우고
...
이런식으로
소수의 배수들을 모두 지워준다.
k = int(input())
array = [1 for _ in range(10000001)]
answer = []
for i in range(2, 10000001):
if array[i]:
answer.append(i)
for j in range(i * 2, 10000001, i):
if j > 10000000:
break
array[j] = 0
print(answer[k-1])
