Project Euler 60

プロジェクトオイラー
http://projecteuler.net/index.php

Q60.
5つの素数の2つ結合した整数がそれぞれ素数となる組で総和が最小のもの

そのような4つの組を求めて、そこに1つ素数を組み合わせて成り立つかどうか調べていくが、総和が最小のものを見つけなければならないので難しい。実行時間は2時間くらいかかった。

from itertools import count
def is_prime(n):

    if n == 1:

        return False

    elif n == 2:

        return True

    elif (n & 1) == 0:

        return False

    

    p = 3

    while p * p <= n:

        if n % p == 0:

            return False

        p += 2

    return True
def gen_prime():

    n = 3

    while True:

        if is_prime(n):

            yield n

        n += 2
def join(m, n):

    mul = 10

    while mul < n:

        mul *= 10

    return m * mul + n
def is_valid_comb(p, c):

    if p <= c[len(c)-1]:

        return False

    if not is_prime(p):

        return False

    for q in c:

        if not is_prime(join(p, q)):

            return False

        if not is_prime(join(q, p)):

            return False

    return True
class gen_comb():

    def __init__(self, c):

        self.comb = c

        self.s = sum(c)

    

    def get_comb(self, n):

        if n < self.s + 3:

            return -1

        else:

            p = n - self.s

            if is_valid_comb(p, self.comb):

                return 1

            else:

                return 0

    

    def sum(self):

        return self.s

    def comb(self):

        return self.comb
def gen(n):

    if n == 1:

        for p in gen_prime():

            yield [ p ]

    else:

        g = gen(n - 1)

        c = [ gen_comb(g.next()), gen_comb(g.next()) ]

        for s in count(c[0].sum() + 3):

            if (s & 1) != (n & 1):

                continue

            b = True

            for e in c:

                det = e.get_comb(s)

                if det == 1:

                    yield e.comb + [ s - e.sum() ]

                elif det == -1:

                    b = False

            

            if b:

                c.append(gen_comb(g.next()))

            if n == 5:

                print s
l = gen(5).next()

print l

print sum(l)