Blog Full Notice
back to main page
오일러 프로젝트 문제 7. 10001번째 소수는. 네이버 블로그
motivation: 네이버 블로그
#오일러 프로젝트 문제 7: 10001번째 소수는? : 네이버 블로그
#problem7_try1.py
'''소수를 크기 순으로 나열하면 2, 3, 5, 7, 11, 13, ... 과 같이 됩니다.
이 때 10,001번째의 소수를 구하세요.'''
#자신이 소수면 자신을 출력, 아니면 0 출력하는 ifprimereturnprime(n) 함수 생성
def ifprimereturnprime(n):
if n==1: return 0
if n==2: return 2
else:
j=0
for i in range(2,n):
if n%i==0: j+=1
if j==0: return n
else: return 0
#n번째 소수를 출력하는 prime(n) 함수 생성
def prime(n):
k=1
while True:
k+=1
if ifprimereturnprime(k)!=0:
n=n-1
if n==0: return k
print(prime(10001))
#print(prime(10001))
답: 104743
코드 실행시간이 10분 정도로 매우 길었다.
에라토스체네스의 채를 알면 빨리 구할 수 있는 것 같다.
공부해 보아야겠다.
+사실 너무 오래 걸려서 다른 코드로 시도해 보았지만 나머지 다른 방법도 시간이 너무 오래 걸려서 그냥 첫번째 문제 풀이 방법으로 문제를 풀었다. 시간도 비슷하게 나왔다..뭐 비슷한 알고리즘으로 구했으니 시간이 비슷하게 걸린 것은 당연하다.
#problem7_try1 copy.py
'''소수를 크기 순으로 나열하면 2, 3, 5, 7, 11, 13, ... 과 같이 됩니다.
이 때 10,001번째의 소수를 구하세요.'''
#자신이 소수면 자신을 출력, 아니면 0 출력하는 ifprimereturnprime(n) 함수 생성
def ifprimereturnprime(n):
if n==1: return 0
if n==2: return 2
else:
j=0
for i in range(2,n):
if n%i==0: j+=1
if j==0: return n
else: return 0
primenumlist=[]
k=1
while len(primenumlist)<10001:
if ifprimereturnprime(k)!=0:
primenumlist.append(k)
k+=1
print(primenumlist[-1])
모두 답은 104743로 동일했다.
댓글남기기