Project Euler. #7. 10001st prime

By | 2013/02/18

Project Euler (http://projecteuler.net/) 문제7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

소수를 순서대로 2, 3, 5, 7, 11 그리고 13을 나열하였을 때, 6번째 소수는 13이다.

10001번째 소수는 무엇인가?


def isPrime(n):
for i in range(2, int(n**(0.5))+1):
if n%i==0:
return False
return True

cnt = 0
num = 1
while cnt<10001: num+=1 if isPrime(num): cnt+=1 print num [/python] Project Euler에 소수와 관련한 문제가 자주 나오다보니 이제 특정 수 n이 소수인지 아닌지를 확인할 때, 2에서 n-1까지의 수로 다 나눠볼 필요도 없이 2에서 n보다 작은 자연수까지만 나눠보면 된다는 건 기본적인 상식이 되어버렸다. 어짜피 n을 소인수분해하면 가장 큰 소인수는 n을 넘지 못하기 때문이다. n보다 작은 소수들로 하나씩 나눠보아도 나누어 떨어지지 않으면 n은 소수이다. 이건 무슨 법칙 이름이 있을 것 같은데... 어쨌든 이렇게 계산하면 계산 시간이 엄청나게 줄어들어서 좋다.

문제 해결 후, 다른 사람들이 짠 코드 중 재밌는게 있나 싶어서 둘러봤는데 이번에는 다들 내가 짠 코드의 맥락과 크게 벗어나지 않은 것 같다.