Project Euler 60

发表于 更新于 分类于 阅读次数： 本文字数： 773 阅读时长 ≈ 1 分钟

Project Euler 60

题目

Prime pair sets

The primes \(3, 7, 109,\) and \(673\), are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking \(7\) and \(109\), both \(7109\) and \(1097\) are prime. The sum of these four primes, \(792\), represents the lowest sum for a set of four primes with this property.

Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.

解决方案

本题的逼近上限难以通过分析方法计算出来，因此直接拟定一个上限，此处的上限定为\(N=10^4\)。

这题可以从图论的角度上考虑简化。如果质数对\((x,y)\)满足题目条件，那么就将\(x\)和\(y\)连结一条边。

那么，这个问题就转化为，在这张图上面找一个大小为\(5\)的团（团：无向图上的一个子图，但是这个子图是一个完全图。）

在我没有了解过networkx库时，我写了第一份代码，它是直接深度优先搜索寻找一个大小为\(5\)的团，并且没有添加太多的优化，最终运行了约\(8\)秒。

使用networkx的find_cliques函数，它可以找到图中的所有团。

另外，寻找图的最大团的算法为Bron–Kerbosch algorithm算法。networkx的find_cliques函数就是基于Bron-Kerbosch算法的迭代版本。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
from tools import get_prime, is_prime

N = 10000
M = 5
pr = get_prime(N)

n = len(pr)
g = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
    for j in range(i):
        x, y = pr[i], pr[j]
        u, v = int(str(x) + str(y)), int(str(y) + str(x))
        if is_prime(u) and is_prime(v):
            g[i][j] = g[j][i] = 1

a = [0 for i in range(M)]
ans = 0


def dfs(p: int, f: int):
    global ans
    if f == M:
        ans = sum([pr[x] for x in a])
        return 1
    while p < n:
        i = 0
        while i < f:
            if g[a[i]][p] == 0:
                break
            i += 1
        if i == f:
            a[f] = p
            if dfs(p + 1, f + 1):
                return 1
        p += 1
    return 0


dfs(0, 0)
print(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from tools import get_prime, is_prime
import networkx as nx

G = nx.Graph()
N = 10000
M = 5
pr = get_prime(N)

n = len(pr)
for i in range(n):
    for j in range(i):
        x, y = pr[i], pr[j]
        u, v = int(str(x) + str(y)), int(str(y) + str(x))
        if is_prime(u) and is_prime(v):
            G.add_edge(i, j)

a = [b for b in nx.find_cliques(G) if len(b) == M]
ans = min((sum(pr[x] for x in pos) for pos in a))
print(ans)