読者です 読者をやめる 読者になる 読者になる

Problem 35 解答

Project Euler

先日紹介したProblem 35の解答を書いてみます。


Problem 35

197は巡回素数と呼ばれる.
桁を回転させたときに得られる数
197, 971, 719 が全て素数だからである.
100未満には巡回素数が13個ある:
2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, および97である.
100万未満の巡回素数は何個か?


2通りの解き方を紹介したので、
それぞれの方法での実装と実行時間を書いてみます。


方法1
1, 3, 7, 9 の4種類の数字からなる全ての100万未満の自然数に対して
巡回素数であるか否かを判定する。

ALLOWED_NUM = [1, 3, 7, 9]
def next(num_list):
    target_id = len(num_list) - 1
    
    while 0 <= target_id:
        id = ALLOWED_NUM.index(num_list[target_id])
        
        if id < len(ALLOWED_NUM) - 1:
            # 繰り上がりなし
            num_list[target_id] = ALLOWED_NUM[id + 1]
            return True
        
        # 繰り上がりあり
        num_list[target_id] = ALLOWED_NUM[0]
        target_id -= 1
    return False

def gen_int(num_list):
    return reduce(lambda a, b: a * 10 + b, num_list, 0)

def is_prime(n):
    if n == 2:
        return True
    if n < 2 or n % 2 == 0:
        return False
    m = 3
    while m ** 2 <= n:
        if n % m == 0:
            return False
        m += 2
    return True

def rotate(num_list):
    return num_list[1:] + [num_list[0]]

def is_circular_prime(num_list):
    for d in xrange(len(num_list)):
        if not is_prime(gen_int(num_list)):
            return False
        num_list = rotate(num_list)
    return True

result = [2, 3, 5, 7]
for k in xrange(2, 7):
    num_list = [ALLOWED_NUM[0]] * k
    
    to_be_continued = True
    while to_be_continued:
        if is_circular_prime(num_list):
            result.append(gen_int(num_list))
        
        to_be_continued = next(num_list)

print len(result)

実行時間は 0.407 [sec] でした。


方法2
100万未満の全ての素数をリストアップし、
1, 3, 7, 9の4種類の数字からなるものに対して巡回素数であるか否かを判定する。

def gen_int(num_list):
    return reduce(lambda a, b: a * 10 + b, num_list, 0)

prime_list = range(10 ** 6)
prime_list[0] = 0
prime_list[1] = 0
for i in xrange(2, len(prime_list) / 2):
    if prime_list[i] == 0:
        continue
    m = i * 2
    while m < len(prime_list):
        prime_list[m] = 0
        m += i

def is_prime(n):
    return prime_list[n] > 0

def rotate(num_list):
    return num_list[1:] + [num_list[0]]

def is_circular_prime(num_list):
    for d in xrange(len(num_list)):
        if not is_prime(gen_int(num_list)):
            return False
        num_list = rotate(num_list)
    return True

def consists_of_1379(num_list):
    for d in num_list:
        if not d in [1, 3, 7, 9]:
            return False
    return True

result = [2, 3, 5, 7]
for n in xrange(11, 10 ** 6):
    num_list = map(int, str(n))
    if not consists_of_1379(num_list):
        continue
    if is_circular_prime(num_list):
        result.append(n)

実行時間は 12.562 [sec] でした。


エラトステネスのふるい法はもっと高速化すべきですが、
何度も素数判定を行う場合はmemoize化すればよいだけなので
あまり使う機会はないかもしれませんね。


久々にエラトステネスさんのことを思い出した問題でした。