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.
这个花了很长时间，主要是暴力破解的时候一会儿内存爆了，一会儿CPU爆了。
所以不要问我13和1237是怎么回事，都是magic number，最后结果出来还需要cancel。
之前有个7开始的结果，比13的这个还大。
import math
import sys
NOT_PRIME_LIST = []
PRIME_LIST = []
il = range(3, 20000)
IL_PRIME = []
def is_Prime(number):
if number in PRIME_LIST:
return True
if number in NOT_PRIME_LIST:
return False
if number < 2:
return False
for x in range(2, int(math.sqrt(number)) + 1):
if number % x == 0:
NOT_PRIME_LIST.append(number)
return False
PRIME_LIST.append(number)
return True
for i in il:
if (is_Prime(i)):
IL_PRIME.append(i)
print len(IL_PRIME)
print
def concat(a, b):
return eval(str(a)+str(b))
def check_c(m, n):
return is_Prime(concat(n, m)) and is_Prime(concat(m, n))
for a in IL_PRIME:
if a < 13:
continue
for b in IL_PRIME:
if b < 1237:
continue
if b <= a:
continue
if check_c(a, b):
# print a, b
for c in IL_PRIME:
if c < b:
continue
if check_c(b, c) and check_c(a, c):
# print a,b,c
for d in IL_PRIME:
if d < c:
continue
if check_c(a, d) and check_c(b, d) and check_c(c, d):
print a, b, c, d
for e in IL_PRIME:
if e < d:
continue
if check_c(a, e) and check_c(b, e) and check_c(c, e) and check_c(d, e):
print a, b, c, d, e
print a+b+c+d+e