지나가던 개발자
[Python] 백준 9842번(Prime) 문제 풀이 본문
def nthPrime(n):
a = [False, False] + [True] * 999998
Primes = []
for i in range(2, 999998):
if a[i]:
Primes.append(i)
for j in range(i+i, 999998, i):
a[j] = False
return Primes[n-1]
print(nthPrime(int(input())))
[Python] n번째 소수 찾기
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 def nthPrime(n): # To-do # 충분히 큰 크기(1000000 정도)를 가진 리스트를 생성하고 # 에라토스테네스의 체를 사용해 n번..
wlghsp.tistory.com
위 글을 참고하여배껴서 코드를 짰다. 에라토스테네스의 체 알고리즘으로, 이에 관해서는 나중에 포스팅할 생각이다.
간단히 말하자면, 임의의 수 P가 소수라면 P를 제외한 P의 모든 배수는 합성수가 되는 원리를 사용한 알고리즘이다.
'PS > Python' 카테고리의 다른 글
| [Python] 백준 11931번(수 정렬하기 4) 문제 풀이 (0) | 2022.09.15 |
|---|---|
| [Python] 백준 2751번(수 정렬하기 2) 문제 풀이 (0) | 2022.09.15 |
| [Python] 백준 1252번(이진수 덧셈) 문제 풀이 (0) | 2022.09.09 |
| [Python] 백준 4150번(피보나치 수) 문제 풀이 (0) | 2022.09.04 |
| [Python] 백준 2028번(자기복제수) 문제 풀이 (0) | 2022.09.03 |
'PS/Python' Related Articles
more
Comments