10001st prime, Project Euler Problem 7
March 15, 2020
https://projecteuler.net/problem=7
10001番目の素数を求める。まずは愚直に求めてみよう。
Solution 1 #
from datetime import datetime
def is_prime(num):
for d in range(2, num):
if num % d == 0:
return False
return True
# test is_prime()
print(is_prime(2)) # True
print(is_prime(3)) # True
print(is_prime(4)) # False
print(is_prime(17)) # True
def find_prime(nth):
count = 0
num = 1
while count < nth:
num += 1
if is_prime(num):
count += 1
return num
# test find_prime()
print(find_prime(6)) # 13
start_time = datetime.now()
print(find_prime(10001)) # ?
exec_time = datetime.now() - start_time
print(exec_time)
答えは求められた。ただし処理時間が、
0:00:45.135762
45秒は時間かかりすぎだ。改善をしよう。
Solution 2 #
素因数かどうかはその数より小さい素因数でのみ割り切れるかをチェックすればよい。それまでに求めた素因数はprimesリストに保持するようにした。is_prine()関数が引数１つで一意な結果が返るものじゃなくなったのでfind_prime()関数内に統合している。
from datetime import datetime
def find_prime(nth):
num = 1
primes = []
while len(primes) < nth:
num += 1
is_prime = True
for p in primes:
if num % p == 0:
is_prime = False
break
if is_prime:
primes.append(num)
return num
# test find_prime()
print(find_prime(1)) # 2
print(find_prime(6)) # 13
start_time = datetime.now()
print(find_prime(10001)) # ?
exec_time = datetime.now() - start_time
print(exec_time)
これで処理時間は、
0:00:04.344577
約1/10の時間で求められるようになった。