Problem 37

またまたプロジェクトオイラーです。
また素数か、という感じが否めませんが、
素数はそれほどまでに人の関心を惹きつけるということでしょう。


Problem 37

3797は面白い性質を持っている.
まずそれ自身が素数であり, 左から右に桁を除いたときに
全て素数になっている.
(3797, 797, 97, 7).

同様に右から左に桁を除いたときも
全て素数である.
(3797, 379, 37, 3).

右から切り詰めても左から切り詰めても
素数になるような素数は11個しかない. 
総和を求めよ.

注: 2, 3, 5, 7を切り詰め可能な素数とは考えない.


最小位及び最大位の数字が 3 か 7 でなければならない、
というのはすぐにわかることですが、
それ以外にも絞る条件はあるでしょうか。
逆に絞らないと題意を満たす素数を11個見つけるまで
無限ループを回すというゴリ押しな方法になってしまいます。
(多分それでも解はすぐに見つかるような気がしますが。)


…。


さ、ゴリ押しのプログラムを実行してみましょう。

def is_prime(n):
    if n in [2, 3]:
        return True
    if n % 2 == 0 or n % 3 == 0 or n < 3:
        return False
    m = 5
    d = 2
    while m ** 2 <= n:
        if n % m == 0:
            return False
        m += d
        d = 6 - d
    return True

found_numbers = []
n = 11
while len(found_numbers) < 11:
    n += 1
    
    sn = str(n)
    found = True
    for i in xrange(1, len(sn)):
        if not is_prime(int(sn[:i])):
            found = False
            break
        if not is_prime(int(sn[i:])):
            found = False
            break
    
    if not found:
        continue
    if not is_prime(n):
        continue
    
    found_numbers.append(n)

print sum(found_numbers)

7.625 [sec] で実行でき、答えは 748317 となります。


ちなみに、いつもの素数判定コードじゃつまらないなと思い
is_prime()関数を少しいじってあります。
これはnを3, 5, 7, 9, 11, …という奇数で割るのではなく、
5, 7, 11, 13, 17, 19, 23, 25, 29, 31 … というように
3の倍数を除いた奇数で割っていくように変更したものです。
変更前は 8.234 [sec] かかりました。


久々のどうでも良い高速化でした。
ちなみに上記の高速化手法は
「コンピュータと素因子分解」(和田秀男先生 著)
という名著から学びました。
これは小学校卒業の際に、
低学年の頃の担任の先生からいただいた本です。
↓のAmazonの商品は1999年出版とありますが、
きっと再版されたものかと思います。

コンピュータと素因子分解

コンピュータと素因子分解