Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
1
Help us understand the problem. What is going on with this article?
@yopya

Project Euler 60「素数ペア集合」

More than 3 years have 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))

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

1
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  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
yopya
自然に囲まれた田舎で働きたい。 田舎でPythonの仕事ないっすか?

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
1
Help us understand the problem. What is going on with this article?