지나가던 개발자

[Python] 백준 15965번(K번째 소수) 문제 풀이 본문

PS/Python

[Python] 백준 15965번(K번째 소수) 문제 풀이

KwonYongHyeon 2022. 10. 23. 20:55

 

n = int(input())

A = [False, False] + [True] * 7368788
Primes = []

for i in range(2, 7368788):
    if A[i]:
        Primes.append(i)
        for j in range(i+i, 7368788, i):
            A[j] = False

print(Primes[n-1])

 

에라토스테네스의 체 알고리즘을 사용했다. (덕분에 메모리가 145980KB...)

 

50만번째 소수는 7368788이다.

저작자표시 (새창열림)

'PS > Python' 카테고리의 다른 글

[Python] 백준 24175번(Tokyo2020) 문제 풀이  (1) 2022.10.25
[Python] 백준 13985번(Equality) 문제 풀이  (0) 2022.10.24
[Python] 백준 4355번(서로소) 문제 풀이  (1) 2022.10.22
[Python] 백준 6992번(Arithmetic Sequence) 문제 풀이  (0) 2022.10.22
[Python] 백준 1546번(평균) 문제 풀이  (0) 2022.10.21
'PS/Python' Related Articles more
Comments