[ Project Euler With Python ] 7. 10001st prime

원문 : 10001st prime

---

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 10 001st prime

처음 6 개의 소수를 열거하면: 2, 3, 5, 7, 11, 13 입니다. 우리는 6 번째 소수가 13 임을 알 수 있습니다.

10 001 번째 소수는 무엇인가요?

Brute-Force

일단 Brute-Force 기법으로 10,001 번째 소수를 찾아 보도록 하겠습니다. [ 3. Largest prime factor ] 에서 소수 찾기를 해 봤죠. 물론 list 에다가 넣다가 ( 성능 문제로 ) 실패했지만, 이제는 소수를 모두 찾아야 하는 시점이 왔습니다.

[ 1 ] 에서 언급했듯이 다음과 같은 규칙을 통해 계산을 줄일 수 있습니다.

이 중에서 1, 3, 7, 9 로 끝난다는 것의 의미는 5 의 배수가 아니라는 의미가 됩니다. 그래서 일단 list 에 2, 3, 5 를 넣어 둔 상태로 다음 홀수가 소수 조건에 위배되는지를 검사했습니다. 

def gather_primes( nth ) : primes = list() primes.append( 2 ) primes.append( 3 ) primes.append( 5 ) i = 7 # second prime number, and odd number. while( len( primes ) < nth ) : is_prime = True for p in primes : # for each prime number if 0 == ( i % p ) : # i is evenly divided by prime number is_prime = False # i is not prime number break if is_prime : primes.append( i ) i += 2 # select next odd number if 0 == ( i % 5 ) : # if next odd number is multiple of 5 i + 2 # select next odd number return primes order = 10001 primes = gather_primes( order ) print( primes[ order - 1 ] )

시간이 좀 걸리긴 했지만, 답은 104743 입니다.

Optimization

문제를 풀면 나오는 PDF 를 보니 더 많은 조건을 사용해서 하더군요. 그리고 저처럼 list 를 사용하지도 않습니다. 관심이 있으시면 확인해 보시기 바랍니다.

참고자료

[ 1 ] 소수 ( 수론 ), 위키피디아.