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

Project Euler 60をPythonでやってみる

問題60

英語
https://projecteuler.net/problem=60
日本語
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2060

解答60

今回は難しかったです。
回答もあまり良いものではないかもしれません。
特に難しいのは最小性で答えが見つかっただけでは確認しきれません。

アルゴリズムに関しては次の記事を参考にしました。
https://tasusu.hatenablog.com/entry/20121119/1353331189

記事と同じようにグラフを作り、サイズ5のクリークを見つけるアルゴリズムを使いました。

ただこのアルゴリズムには問題点があります。
それはグラフの頂点となる素数の上限を決める必要があることです。
この上限値が低いと答えを確定できなかったりそもそも答えが見つからなかったりします。
逆に上限値を大きくしすぎるとグラフを作る計算量が大きくなり過ぎてしまいます。
今回は大体の答えがわかっていたため、この上限値を適切な30000と取りましたが、適切な上限値を与えないと良い働きをしないアルゴリズムになってしまいました。

コードは次のようになります。

ProjectEuler60.py
import sympy as sym
import math
import itertools


def is_Prime_Pairs(num1,num2):
    a = int(str(num1) + str(num2))
    if not (sym.isprime(a)):
        return False
    b = int(str(num2) + str(num1))
    return sym.isprime(b)

def del_vertex(edge_dic):
    dic = {prime:prime_set for prime,prime_set in edge_dic.items() if len(prime_set)>3} #次数3以下のvertexを削除
    return {prime: {q for q in prime_set if q in dic.keys()} for prime, prime_set in dic.items()}

def sum_clique(edge_set,p,clique_set):
    global ans_min
    next_clique_set = clique_set|{p}
    if len(next_clique_set) == 1:
        next_set = edge_dic[p]
    else:
        next_set = edge_dic[p] & edge_set

    if len(next_set) < 5-len(next_clique_set):
        return

    if len(next_clique_set) == 4:
        ans = sum(next_clique_set) + min(next_set)
        if ans_min == 0 or ans < ans_min:
            ans_min = ans
            # print(ans_min)
            return
    sort_next = sorted([x for x in next_set if x > max(next_clique_set)])
    for q in sort_next:
        sum_clique(next_set,q,next_clique_set)
    return



num_max =30000
primes = {i for i in sym.primerange(3,num_max)}
primes.remove(5) #5はどこともedgeを持たない
edge_dic = {i:set() for i in primes}

# グラフ作成
for p in primes:
    for q in (q for q in primes if q > p):
        if is_Prime_Pairs(p, q):
            # print((p,q))
            edge_dic[p].add(q)
            edge_dic[q].add(p)
print("Phase1")

# 次数3以下のvertexを削除
edge_dic = del_vertex(edge_dic)
print("Phase2")
# 素数の和が最少のクリークを探す
keys = sorted(edge_dic.keys())
ans_min = 0
for p in keys:
    if ans_min > 0 and p > ans_min:
        break
    sum_clique(set(),p,set())

print(ans_min)

62.598 seconds
グラフ作成だいたいが60sです。

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