Project Euler 58をPythonでやってみる

問題58

英語
https://projecteuler.net/problem=58
日本語
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2058

解答58

正直そこまで工夫はしていません。
4つ進むごとに増加する値が2増える数列になっているのでその通りに進めていき、1周ごとに10%未満になるか調べるだけです。

コードは次のようになります。

ProjectEuler51.py

import math

def is_prime(n):
    for k in range(3, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True


dist = 4
num_of_prime = 3
num_of_all =5
num = 9
while 10*num_of_prime >= num_of_all:
    for i in range(0,3):
        num += dist
        if is_prime(num):
            num_of_prime += 1
    num += dist
    num_of_all += 4
    dist += 2

print(dist-1)

8.469 seconds