[BOJ][Python] 백준 15965번 - K번째 소수

문제 링크: https://www.acmicpc.net/problem/15965

15965번: K번째 소수

 

 

---

문제 풀이

에라토스테네스의 체를 이용하여 문제를 풀었다. 500,000번째 소수까지 구해야해서 한 4백만 쯤 잡았는데도, 런타임 에러가 떴다(indexError). 혹여나 8백만까지 올려봤는데 답은 맞았지만 시간이 너무 오바긴하다. 딱히 질 좋은 문제는 아닌거 같다. 에라토스테네스의 체를 이용하여 소수를 찾아주고 반복문을 이용하여 K번째 소수가 나올때 까지 반복문을 돌려준다.

 

 

코드

	from math import sqrt
	n = 8000000
	prime = [0, 0] + [1] * (n-1)
	for i in range(2, int(sqrt(n))+1):
	j = 2
	while i*j <= n:
	prime[i*j] = 0
	j += 1
	a = 0
	k = int(input())
	for i in range(2, n+1):
	if prime[i] == 1:
	a += 1
	if k == a:
	print(i)
	break

view raw 15965.py hosted with ❤ by GitHub