카테고리 없음

Project Euler 7

_Sudal 2019. 2. 1. 02:52

Question: 


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 number?

문제:

소수를 크기 순으로 나열하면 2, 3, 5, 7, 11, 13, ... 과 같이 됩니다.

이 때 10,001번째의 소수를 구하세요.


Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def findPrime(n):
    import time
    primelist = [2]
    decPrime = 3
    start = time.time()
    while True:
        isPrime = True
        for x in primelist:
            if decPrime % x == 0:
                isPrime = False
                break # if decPrime is not Prime number, break the loop
            else:
                isPrime = True
        if isPrime == True:
            primelist.append(decPrime) # if decPrime is Prime, add into list
        else:
            pass            
        if len(primelist) == n: # if last element of primelist is nth number
            break
        decPrime += 2
    print(primelist[-1])
    print('takes {}seconds'.format(time.time()-start))
cs


처음 만든 솔루션, 4.03s 걸렸다

모든 홀수에 대해 검사하려니 너무 오래 걸렸다.


1
2
3
4
5
6
7
from sympy import sieve
import time
 
start = time.time()
sieve.extend_to_no(10001)
print(sieve[10001])
print("Found in ...{:.5f}s".format(time.time() - start))
cs


sympy 에서 sieve 를 import 했다.

훨씬 간단하고 짧게 걸린다.


0.00033s 걸렸다!

2019/01/29 - [Programming/python] - Module: sympy