Help us understand the problem. What is going on with this article?

Project Euler 60「素数ペア集合」

More than 1 year has passed since last update.

かなり頑張ったんですが、それでも12~13分くらいかかります。
最初に見つかった値が最小値である確証が持てれば30秒程なんですが。
ちなみに初めに書いたコードは驚異の2時間コースでした。

Problem 60 「素数ペア集合」

素数3, 7, 109, 673は非凡な性質を持っている. 任意の2つの素数を任意の順で繋げると, また素数になっている. 例えば, 7と109を用いると, 7109と1097の両方が素数である. これら4つの素数の和は792である. これは, このような性質をもつ4つの素数の集合の和の中で最小である.
任意の2つの素数を繋げたときに別の素数が生成される, 5つの素数の集合の和の中で最小のものを求めよ.

from itertools import count

def hoge(num):
    def get_ans(S, L):
        if len(L) == num:
            #print(sum(L), L)
            ans.append(sum(L))
        else:
            for s in S:
                get_ans(S & primes[s], L + [s])
#
    f = lambda x, y: is_prime(int(x + y)) and is_prime(int(y + x))
    primes, ans = {}, []
    min_under = hoge(num-1) if num > 1 else 0
    for n in count(3, 2):
        if n % 5 == 0 or not is_prime(n):
            continue
        S = set()
        for p in primes.keys():
            if f(str(n), str(p)):
                S.add(p)
        if len(S) >= num-1:
            get_ans(S, [n])
        if ans and  min(ans) <= n + min_under:
            return min(ans)
        primes[n] = S

def is_prime(n):
    if n < 2: return False
    if n == 2: return True
    if n % 2 == 0: return False
    return all(n % i != 0 for i in range(3, int(n ** 0.5) + 1, 2))

print(hoge(5))

最初に書いたコードはこちら

from itertools import count, permutations

def hoge(num):
    f = lambda x, y: is_prime(int(x + y)) and is_prime(int(y + x))
    primes = []
    for i in count(3, 2):
        if not is_prime(i): continue
        l = []
        for n in primes:
            if f(str(i), str(n)): l.append(n)
        if len(l) >= num:
            print(i, l)
            for P in permutations(l, num):
                if all( f(str(p[0]), str(p[1])) for p in permutations(P, 2) ):
                    return i + sum(P)
        primes.append(i)

def is_prime(n):
    if n < 2: return False
    if n == 2: return True
    if n % 2 == 0: return False
    return all(n % i != 0 for i in range(3, int(n ** 0.5) + 1, 2))

print(hoge(5))

最小性も示せてないのにすっごい遅いよ!

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away