Project Euler 60
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 | from tools import get_prime, is_prime |
1 | from tools import get_prime, is_prime |