Project Euler 問題7 「10001番目の素数」

問題

10001番目の素数を求めよ。

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?

コード(Python)

def isPrimeNum(num, primeNums):
    for primeNum in primeNums:
        if num % primeNum == 0:
            return False;
        if primeNum * primeNum > num:
            return True;

def getNextPrimeNum(primeNums):
    num = primeNums[-1] + 1;
    while (isPrimeNum(num, primeNums) == False):
        num += 1;
    return num;

primeNums = [2]
while(len(primeNums) < 10001):
    next = getNextPrimeNum(primeNums)
    primeNums.append(next)
print(primeNums[-1])

処理時間は約0.1秒でした。

# 5行目
if primeNum * primeNum > num:

の処理を抜くと6秒くらいになります。ループを削る工夫って大事なんだなぁ。