小练习：找出一个5个质数的集合，该集合中每两个质数相连接都能产生一个素数

冬雪雪冬

从现在开始我们要开展一批欧拉计划的习题练习。
其实在我们论坛中已有欧拉计划的板块，可能有些鱼油还没注意到。
什么是欧拉计划：http://bbs.fishc.com/thread-60405-1-1.html
我们欧拉板块现已给出了200余题，这批练习将从欧拉计划中选题。其实用python语言完成有很多的优势，可以更简洁更方便的实现。
如果大家有兴趣也可浏览欧拉的英文网站：https://projecteuler.net/archives
这里已经有了500余题。

                               
登录/注册后可看大图

题目要求：
以python语言完成，如果是python2请注明。
程序以代码文字格式发帖。
注重程序效率和创意。
答题在一周内完成，即2.20 10：00之前，其后将公开大家的答案，并评比成绩。
另程序和答案可以在网上搜到，希望大家独立完成。题目不难，大家看看谁的效率高。

----回帖需写明解题思路，鼓励在程序



题目：

质数 3, 7, 109, 和 673 是值得注意的。将其中任意两个质数以任何顺序相连接产生的结果都是质数。例如，取 7 和 109，连接而成的 7109 和 1097 都是质数。这四个质数的和是 792，这也是满足这个性质的四个质数集合的最小总和。

找出满足这个性质的五个质数的集合中，集合数之和最小的。算出这个最小的和。

附加题：
这个题目 @jerryxjr1220 曾经在本板块向大家介绍过，大家可以再练习一下。

电脑上的每个字符都有一个唯一编码，通用的标准是 ASCII (American Standard Code for Information Interchange 美国信息交换标准编码)。例如大写A = 65， 星号(*) = 42，小写k = 107。

一种现代加密方法是用一个密钥中的给定值，与一个文本文件中字符的 ASCII 值进行异或。使用异或方法的好处是对密文使用同样的加密密钥可以得到加密前的内容。例如，65 XOR 42 = 107, 然后 107 XOR 42 = 65。

对于不可攻破的加密，密钥的长度与明文信息的长度是一样的，而且密钥是由随机的字节组成的。用户将加密信息和加密密钥保存在不同地方，只有在两部分都得到的情况下，信息才能被解密。

不幸的是，这种方法对于大部分用户来说是不实用的。所以一种修改后的方案是使用一个密码作为密钥。如果密码比信息短，那么就将其不断循环直到明文的长度。平衡点在于密码要足够长来保证安全性，但是又要足够短使用户能够记得。

你的任务很简单，因为加密密钥是由三个小写字母组成的。附件（扩展名从rar改为txt）包含了加密后的 ASCII 码，并且已知明文是由常用英语单词组成。使用该文件来解密信息，然后算出明文中字符的 ASCII 码之和。

jerryxjr1220

之前的python小练习正好讲到了“广度优先搜索”，“深度优先搜索”和“A*算法”，这题正好可以利用这3种方法来求解，顺便我们可以比较一下这3种方法之间的效率。
第一种方法：广度优先搜索
思路： 既然是广度优先搜索，当然是按照节点，从上到下依次加入候选列表，然后依次进行判断（顺序是从前到后），看是否符合条件要求（即两两组合能构成素数），如果符合则再加入候选列表，如果不符合就判断下一个。（我其中用了字典的方法帮助加快搜索）
代码：

1. import time
   
2. start = time.time()
   
3. primes = [True]*10000
   
4. primes[0], primes[1] = False, False
   
5. for i, prime in enumerate(primes):
   
6.         if prime:
   
7.                 for j in range(i*i,10000,i):
   
8.                         primes[j] = False
   
9. plist = [k for k, trueprime in enumerate(primes) if trueprime]
   
10. plist.remove(2)
    
11. plist.remove(5)
    
12. 
    
13. def isprime(n):
    
14.         global plist,primes
    
15.         if n<10000:
    
16.                 return primes[n]
    
17.         else:
    
18.                 for p in plist:
    
19.                         if n % p == 0: return False
    
20.                         if p*p > n: return True
    
21. 
    
22. queue = [[each] for each in plist]
    
23. visited = {}
    
24. while len(queue)>0:
    
25.         qu = queue.pop(0)
    
26.         for p in plist:
    
27.                 if p in qu:
    
28.                         continue
    
29.                 flag = True
    
30.                 for q in qu:
    
31.                         ss = (p,q)
    
32.                         if ss not in visited:
    
33.                                 if isprime(int(str(p)+str(q))) and isprime(int(str(q)+str(p))):
    
34.                                         visited[ss] = True
    
35.                                 else:
    
36.                                         visited[ss] = False
    
37.                                         flag = False
    
38.                                         break
    
39.                         else:
    
40.                                 if visited[ss] == False:
    
41.                                         flag = False
    
42.                                         break
    
43.                 if flag:
    
44.                         qu.append(p)
    
45.                         if len(qu) > 4:
    
46.                                 print('Bingo!', qu)
    
47.                                 print(sum(qu))
    
48.                                 print('BFS--Time used: %.3f sec' % (time.time()-start))
    
49.                                 exit()
    
50.                         queue.append(qu)

复制代码

输出：
Bingo! [5701, 13, 5197, 6733, 8389]
26033
BFS--Time used: 13.709 sec

第二种方法：深度优先搜索
思路：利用回溯法进行搜索判断，递归深度最大5层。深度优先搜索在搜索范围很大，而搜索深度又很浅的情况下，优势非常明显（比如本题）。
代码：

1. import time
   
2. start = time.time()
   
3. primes = [True]*10000
   
4. primes[0], primes[1] = False, False
   
5. for i, prime in enumerate(primes):
   
6.         if prime:
   
7.                 for j in range(i*i,10000,i):
   
8.                         primes[j] = False
   
9. plist = [str(k) for k, trueprime in enumerate(primes) if trueprime]
   
10. plist.remove('2')
    
11. plist.remove('5')
    
12. visited = {}
    
13. 
    
14. def isprime(n):
    
15.         global plist,primes
    
16.         if n<10000:
    
17.                 return primes[n]
    
18.         else:
    
19.                 for p in plist:
    
20.                         p = int(p)
    
21.                         if n % p == 0: return False
    
22.                         if p*p > n: return True
    
23. 
    
24. def find(p=0,lst=[]):
    
25.         global plist,visited
    
26.         if len(lst) > 4:
    
27.                 print('Bingo!', lst)
    
28.                 print(sum([int(i) for i in lst]))
    
29.                 print('DFS--Time used: %.3f sec' % (time.time()-start))
    
30.                 exit()
    
31.         if p >= len(plist): return
    
32.         for q in range(p,len(plist)):
    
33.                 a = plist[q]
    
34.                 if len(lst) == 0:
    
35.                         lst.append(a)
    
36.                         find(p+1,lst)
    
37.                         lst.pop()
    
38.                 else:
    
39.                         flag = True
    
40.                         for b in lst:
    
41.                                 ss = (a,b)
    
42.                                 if ss not in visited:
    
43.                                         if isprime(int(a+b)) and isprime(int(b+a)):
    
44.                                                 visited[ss] = True
    
45.                                         else:
    
46.                                                 visited[ss] = False
    
47.                                                 flag = False
    
48.                                                 break
    
49.                                 else:
    
50.                                         if visited[ss] == False:
    
51.                                                 flag = False
    
52.                                                 break
    
53.                         if flag:
    
54.                                 lst.append(a)
    
55.                                 find(p+1,lst)
    
56.                                 lst.pop()
    
57. find()

复制代码

输出：
Bingo! ['13', '5197', '5701', '6733', '8389']
26033
DFS--Time used: 4.441 sec

第三种方法：A*算法：
思路：A*算法是综合了广度优先搜索和深度优先搜索的算法，代码结构几乎和广度优先搜索一致，但是搜索顺序却是从后往前（由于满足条件新加入的候选组合也是加入在列表的末尾），所以实际搜索顺序又是按照了深度优先搜索的方法，如果一条子路径一直能满足条件，则优先搜索新加入的子路径，直到新的子路径不满足要求，再切换到下一个候选组合。所以这个方法在搜索宽度很大而搜索深度又比较浅的情况下（比如本题），比起广度优先算法要快很多。

1. import time
   
2. start = time.time()
   
3. primes = [True]*10000
   
4. primes[0], primes[1] = False, False
   
5. for i, prime in enumerate(primes):
   
6.         if prime:
   
7.                 for j in range(i*i,10000,i):
   
8.                         primes[j] = False
   
9. plist = [k for k, trueprime in enumerate(primes) if trueprime]
   
10. plist.remove(2)
    
11. plist.remove(5)
    
12. 
    
13. def isprime(n):
    
14.         global plist,primes
    
15.         if n<10000:
    
16.                 return primes[n]
    
17.         else:
    
18.                 for p in plist:
    
19.                         if n % p == 0: return False
    
20.                         if p*p > n: return True
    
21. 
    
22. queue = [[each] for each in plist]
    
23. visited = {}
    
24. while len(queue)>0:
    
25.         qu = queue.pop()
    
26.         for p in plist:
    
27.                 if p in qu:
    
28.                         continue
    
29.                 flag = True
    
30.                 for q in qu:
    
31.                         ss = (p,q)
    
32.                         if ss not in visited:
    
33.                                 if isprime(int(str(p)+str(q))) and isprime(int(str(q)+str(p))):
    
34.                                         visited[ss] = True
    
35.                                 else:
    
36.                                         visited[ss] = False
    
37.                                         flag = False
    
38.                                         break
    
39.                         else:
    
40.                                 if visited[ss] == False:
    
41.                                         flag = False
    
42.                                         break
    
43.                 if flag:
    
44.                         qu.append(p)
    
45.                         if len(qu) > 4:
    
46.                                 print('Bingo!', qu)
    
47.                                 print(sum(qu))
    
48.                                 print('A*--Time used: %.3f sec' % (time.time()-start))
    
49.                                 exit()
    
50.                         queue.append(qu)

复制代码

输出：
Bingo! [8389, 13, 5197, 5701, 6733]
26033
A*--Time used: 5.218 sec

结论：
当搜索宽度较大，搜索深度又很浅的情况下（比如本题），效率从高到低依次为：深度优先搜索>A*算法>广度优先搜索。
同理，可以推断，当搜索宽度很小，搜索深度又很深的情况下，效率从高到低依次为：广度优先搜索>A*算法>深度优先搜索。
而当搜索宽度和深度都差不多或者不确定的情况下，A*算法则有比较明显的优势（效率几乎接近最优算法，而且程序代码比较容易写，不用考虑递归（对于新手比较容易掌握））。

余欲渔

这边电脑有点差，没跑出结果，感觉上没错

1. def zs(n):
   
2.     import math
   
3.     if n%2==0:
   
4.         return False
   
5.     elif n%3==0:
   
6.         return False
   
7.     else:
   
8.         r = math.floor(math.sqrt(n))
   
9.         f = 5
   
10.         while f <= r:
    
11.             if n % f == 0:
    
12.                 return False
    
13.             if n %(f+2) == 0:
    
14.                 return False
    
15.             f += 6
    
16.         return True
    
17. 
    
18. def jc(a):
    
19.     for i in range(4):
    
20.         for j in range(i+1,5):
    
21.             if zs(int(str(a[i])+str(a[j])))==False or zs(int(str(a[j])+str(a[i])))==False:
    
22.                 return False
    
23.     return True
    
24. jihe=[]
    
25. i=3
    
26. while i<10000:   
    
27.     if zs(i):
    
28.         jihe.append(i)
    
29.     i+=1
    
30. ljihe=len(jihe)
    
31. x1=0
    
32. while x1<(ljihe-4):
    
33.     for x2 in range(x1+1,ljihe-3):
    
34.         for x3 in range(x2+1,ljihe-2):
    
35.             for x4 in range(x3+1,ljihe-1):               
    
36.                 for x5 in range(x4+1,ljihe):
    
37.                     jieguo=[jihe[x1],jihe[x2],jihe[x3],jihe[x4],jihe[x5]]
    
38.                     if jc(jieguo):
    
39.                         print(sum(jieguo))
    
40.                         x1=ljihe
    
41.     x1+=1
    
42. 
    
43.                     
    

复制代码

jerryxjr1220

余欲渔 发表于 2017-2-13 15:28
这边电脑有点差，没跑出结果，感觉上没错

你这样穷举是不可能算出结果的，10000以内的质数有1229个，5个嵌套循环基本上你需要循环1229**5=2803879945797149次，假设你的电脑可以1秒钟进行100万次循环（实际上达不到的），总共需要88.9年才能完成运算

Craigyu

尽力了，得出结论12秒，但是跑完所有10000以内的质数要10分钟
学习一下楼上的看能怎么改

1. from time import time
   
2. stime = time()
   
3. 
   
4. def prime(n):  #判定质数
   
5.     if n < 2:
   
6.         return False
   
7.     if n ==2 or n == 3:
   
8.         return True
   
9.     if n % 2 == 0:
   
10.         return False
    
11.     for j in range(3,int(n ** 0.5)+1, 2):  
    
12.         if n % j == 0:  
    
13.             return False  
    
14.     return True
    
15. 
    
16. def verd(a, b):        #判定左右组合
    
17.     if prime(int(str(a)+str(b))) == True and prime(int(str(b)+str(a))) == True:
    
18.         return True
    
19. 
    
20. primes = [] # 生成10000以内的质数表
    
21. for i in range(3, 10001):
    
22.     if prime(i) == True and i != 5:
    
23.         primes.append(i)
    
24. 
    
25. sets = []
    
26. 
    
27. for a in range(len(primes)):  #判断两个数组合满足，再寻找下一个数
    
28.     for b in range(a + 1, len(primes)):
    
29.         if verd(primes[a], primes[b]) == True:
    
30.             for c in range(b + 1, len(primes)):
    
31.                 if verd(primes[a], primes[c]) == True and verd(primes[b], primes[c]) == True:
    
32.                     for d in range(c + 1, len(primes)):
    
33.                         if verd(primes[a], primes[d]) == True and verd(primes[b], primes[d]) == True and verd(primes[c], primes[d]) == True:
    
34.                             for e in range(d + 1, len(primes)):
    
35.                                 if verd(primes[a], primes[e]) == True and verd(primes[b], primes[e]) == True and verd(primes[c], primes[e]) == True and verd(primes[d], primes[e]):
    
36.                                     print(primes[a], primes[b], primes[c], primes[d], primes[e], '总和是', primes[a] + primes[b] + primes[c] + primes[d] + primes[e])
    
37.                                     print(time()-stime)
    
38.                                     sets.append([primes[a], primes[b], primes[c], primes[d], primes[e]])
    
39.                                     
    
40. print(sets)                        
    
41. print(time()-stime)
    

复制代码

飘飞的白杨

1. 
   
2. def primes(N):
   
3.     '''素数表（不含 2 和 5）'''
   
4.     l =  int(N**0.5) + 1
   
5.     prime = [False, False] + [True] * (N-1)
   
6.     for i in range(2, l):
   
7.         if prime[i]:
   
8.             for j in range(2, N//i + 1):
   
9.                 if prime[j*i]:
   
10.                     prime[j*i] = False
    
11.     return tuple(i for i in range(len(prime)) if prime[i] and i != 2 and i != 5)
    
12. def isprime(n):
    
13.     '''判断是否是素数'''
    
14.     if n <= 1: return False
    
15.     if n == 2: return True
    
16.     for i in primes_tuple:
    
17.         if i*i > n: return True
    
18.         if n % i == 0: return False
    
19.     for i in range(primes_tuple[-1]+2, int(n**0.5)+1, 2):
    
20.         if n % i == 0: return False
    
21.     return True
    
22. def isprime_list_num(l, p):
    
23.     '''判断 l 中的所有数与 p 拼接是不是素数'''
    
24.     if l == []: return True
    
25.     flag = True
    
26.     p = str(p)
    
27.     for i in l:
    
28.         if (i, p) in dict_p:
    
29.             if not dict_p[(i, p)]:
    
30.                 flag = False
    
31.                 break
    
32.         if not isprime(int(str(i)+p)):
    
33.             dict_p[(i, p)] = False
    
34.             flag = False
    
35.             break
    
36.         elif not isprime(int(p+str(i))):
    
37.             dict_p[(i, p)] = False
    
38.             flag = False
    
39.             break
    
40.         else:
    
41.             dict_p[(i, p)] = True
    
42.     return flag
    
43. X = 10000
    
44. dict_p = {} # 因为有很多重复判断，故用字典储存判断结果
    
45. primes_tuple = primes(X)
    
46. def progrem60():
    
47.     for p1 in primes_tuple:
    
48.         for p2 in primes_tuple:
    
49.             if p2 <= p1: continue
    
50.             if isprime_list_num([p1], p2):
    
51.                 for p3 in primes_tuple:
    
52.                     if p3 <= p2: continue
    
53.                     if isprime_list_num([p1, p2], p3):
    
54.                         for p4 in primes_tuple:
    
55.                             if p4 <= p3: continue
    
56.                             if isprime_list_num([p1, p2, p3], p4):
    
57.                                 for p5 in primes_tuple:
    
58.                                     if p5 <= p4: continue
    
59.                                     if isprime_list_num([p1, p2, p3, p4], p5):
    
60.                                         return [p1, p2, p3, p4, p5]
    
61. print(progrem60())
    

复制代码

余欲渔

jerryxjr1220 发表于 2017-2-13 15:46
你这样穷举是不可能算出结果的，10000以内的质数有1229个，5个嵌套循环基本上你需要循环1229**5=28038799 ...

我说吗，一直跑不出结果，看来还是得从算法入手改改

余欲渔

Craigyu 发表于 2017-2-13 17:23
尽力了，得出结论12秒，但是跑完所有10000以内的质数要10分钟
学习一下楼上的看能怎么改

这样改过确实节约很多不必要的计算，我就不另外发了，毕竟看过你这个，我改的话大体也是像你个样子

余欲渔

那就把附加题做做吧
我分了两段，第一段是用空格异或判断密码，代码如下：

1. f=open('p059_cipher.txt')
   
2. f.seek(0,2)
   
3. x=f.tell()
   
4. f.seek(0,0)
   
5. yuanwen=[]
   
6. a=''
   
7. for i in range(x):              #这段循环来把逗号分隔的数字分开，这样分显得很笨拙- -。。
   
8.     r=f.read(1)
   
9.     if r.isdigit():
   
10.         a+=r
    
11.     else:
    
12.         if a!='':
    
13.             yuanwen.append(a)
    
14.         a=''
    
15. f.close()
    
16. kongge=[]
    
17. for i in yuanwen:
    
18.     kongge.append(int(i)^32)         #异或空格
    
19. beixuan=[[0,0],[0,0],[0,0],[0,0],[0,0]]          #用5个备选，避免干扰的可能性，以便自己择优选择
    
20. bset=set(kongge)
    
21. for i in bset:            #按出现频率放入备选列
    
22.     cs=kongge.count(i)
    
23.     beixuan.sort()
    
24.     if cs>beixuan[0][0]:
    
25.         beixuan[0][0]=cs
    
26.         beixuan[0][1]=i
    
27. for i in range(5):   
    
28.     print(chr(beixuan[i][1]),beixuan[i][1])

复制代码

1. = RESTART: C:/Users/ASUS/AppData/Local/Programs/Python/Python35-32/文件加密解密.py =
   
2. * 42
   
3. ! 33
   
4. g 103
   
5. d 100
   
6. o 111

复制代码

结果出现频率最高的5个字符是 *  ！   g  d  o，那结果就明摆着了，god
再有下面这段代码来翻译成明文：

1. f=open('p059_cipher.txt')
   
2. f.seek(0,2)
   
3. x=f.tell()
   
4. f.seek(0,0)
   
5. yuanwen=[]
   
6. a=''
   
7. for i in range(x):
   
8.     r=f.read(1)
   
9.     if r.isdigit():
   
10.         a+=r
    
11.     else:
    
12.         if a!='':
    
13.             yuanwen.append(a)
    
14.         a=''
    
15. f.close()
    
16. mima=[103,111,100]
    
17. la=len(yuanwen)
    
18. yiwen=''
    
19. he=0
    
20. for i in range(la):
    
21.     x=int(yuanwen[i])^mima[i%3]
    
22.     yiwen+=chr(x)
    
23.     he+=x
    
24. 
    
25. print(yiwen)
    
26. print(he)

复制代码

1. RESTART: C:/Users/ASUS/AppData/Local/Programs/Python/Python35-32/文件加密解密-2.py
   
2. (The Gospel of John, chapter 1) 1 In the beginning the Word already existed. He was with God, and he was God. 2 He was in the beginning with God. 3 He created everything there is. Nothing exists that he didn't make. 4 Life itself was in him, and this life gives light to everyone. 5 The light shines through the darkness, and the darkness can never extinguish it. 6 God sent John the Baptist 7 to tell everyone about the light so that everyone might believe because of his testimony. 8 John himself was not the light; he was only a witness to the light. 9 The one who is the true light, who gives light to everyone, was going to come into the world. 10 But although the world was made through him, the world didn't recognize him when he came. 11 Even in his own land and among his own people, he was not accepted. 12 But to all who believed him and accepted him, he gave the right to become children of God. 13 They are reborn! This is not a physical birth resulting from human passion or plan, this rebirth comes from God.14 So the Word became human and lived here on earth among us. He was full of unfailing love and faithfulness. And we have seen his glory, the glory of the only Son of the Father.
   
3. 107359
   
4. >>>

复制代码

不分两段的话   不知道怎么来合理的判断密码

余欲渔

我上面第一段代码的结果来看，dog也是可能的，忽略了。如果不用空格异或而选用遍历26个字母，也能达到同样效果，这题来看用遍历结果就唯一了

1. f=open('p059_cipher.txt')
   
2. f.seek(0,2)
   
3. x=f.tell()
   
4. f.seek(0,0)
   
5. yuanwen=[]
   
6. a=''
   
7. for i in range(x):              
   
8.     r=f.read(1)
   
9.     if r.isdigit():
   
10.         a+=r
    
11.     else:
    
12.         if a!='':
    
13.             yuanwen.append(a)
    
14.         a=''
    
15. f.close()
    
16. a=[]
    
17. lyw=len(yuanwen)
    
18. for mm in range(97,123):
    
19.     a.append([])
    
20.     for i in range(3):
    
21.         a[mm-97].append([])
    
22.         for j in range(i,lyw,3):
    
23.             a[mm-97][i].append(int(yuanwen[j])^mm)
    
24. beixuan=[[],[],[]]
    
25. for x in range(26):
    
26.     for y in range(3):
    
27.         for z in a[x][y]:
    
28.             aa=1
    
29.             if z>122 :
    
30.                 aa=0
    
31.                 break
    
32.             if z<31:
    
33.                 aa=0
    
34.                 break
    
35.         if aa ==1:beixuan[y].append(chr(x+97))
    
36. print(beixuan)
    

复制代码

那备选结果就有：

1. RESTART: C:\Users\Administrator\AppData\Local\Programs\Python\Python35-32\test.py
   
2. [['f', 'g'], ['l', 'n', 'o'], ['d']]
   
3. >>>

复制代码

这个结果来选的话也只有god是一个单词了

jerryxjr1220

余欲渔 发表于 2017-2-15 17:53
那就把附加题做做吧
我分了两段，第一段是用空格异或判断密码，代码如下：

回答你的问题：
http://bbs.fishc.com/forum.php?mod=viewthread&tid=78764&ctid=503

Craigyu

1. from collections import Counter
   
2. 
   
3. f = open('p059_cipher.txt')
   
4. lst = f.read().split(sep = ',')
   
5. f.close()
   
6. lst1 = lst[::3]
   
7. lst2 = lst[1::3]
   
8. lst3 = lst[2::3]
   
9. 
   
10. y1 = Counter(lst1).most_common(1)
    
11. y2 = Counter(lst2).most_common(1)
    
12. y3 = Counter(lst3).most_common(1)
    
13. 
    
14. hfs = [' ', 'a', 'e', 'i', 't'] #高频字符
    
15. 
    
16. for a in hfs:
    
17.     for b in hfs:
    
18.         for c in hfs:
    
19.             p1 = ord(a)^int(y1[0][0]) # 把统计最多的字符按高频字符解
    
20.             p2 = ord(b)^int(y2[0][0])
    
21.             p3 = ord(c)^int(y3[0][0])
    
22.             if p1 in range(97, 123)and p2 in range(97, 123) and p3 in range(97, 123): #解出为小写字母的，用于解密整篇文档
    
23.                 pw = [chr(p1), chr(p2), chr(p3)] * int(len(lst)/3 + 1)
    
24.                 text = ''
    
25.                 for i in range(len(lst)):
    
26.                     text = text + chr(int(lst[i])^ord(pw[i]))
    
27.                 print(text)
    
28.                 ver = input('continue or not')
    
29.                 if ver == 'n':
    
30.                     break

复制代码

yay

学习

芒果加黄桃

1. # encoding:utf-8
   
2. # 寻找特殊质数  3,7,109,673已任何形式组合比如37  73  7109  1097 都是质数
   
3. # 寻找满足条件的  和最小的五个质数，满足该条件
   
4. from time import time
   
5. from math import sqrt
   
6. def getPrimes(N):
   
7.     primes = [True] * N
   
8.     primes[0], primes[1] = False, False
   
9.     for i, prime in enumerate(primes):
   
10.         if prime:
    
11.             for j in range(i * i, N, i):
    
12.                 primes[j] = False
    
13.     return [k for k, v in enumerate(primes) if v ]
    
14. def isPrime(n, l_pr):
    
15.     # 不考虑1
    
16.     if n < 4:
    
17.         return True
    
18.     if n % 2 == 0 or n % 3 == 0 :
    
19.         return False
    
20.     t = int(sqrt(n))
    
21.     for i in l_pr:
    
22.         if i > t:
    
23.             return True
    
24.         if n % i == 0:
    
25.             return False
    
26.     return True
    
27. def findNums(l_pr, l_primes, N, l_result):
    
28.     if N == 1 and len(l_result) < 1:
    
29.         l_result.append(min(l_primes))
    
30.     else:
    
31.         if len(l_result) < N:
    
32.             findNums(l_pr, l_primes, N - 1, l_result)
    
33.             for i in [x for x in l_primes if x > max(l_result)]:
    
34.                 flag = True
    
35.                 for j in l_result:
    
36.                     if not (isPrime(int(str(j) + str(i)), l_pr)  
    
37.                             and isPrime(int(str(i) + str(j)), l_pr)):
    
38.                         flag = False
    
39.                         break
    
40.                 if flag:
    
41.                     l_result.append(i)
    
42.                     return         
    
43. def euler060(N=10000):
    
44.     l_primes = getPrimes(N)
    
45.     l_result = [2]
    
46.     l_pr = [x for x in l_primes]
    
47.     findNums(l_pr, l_primes, 5, l_result)
    
48.     while len(l_result) < 5:
    
49.         l_primes = [i for i in l_pr if i > max(l_result)]
    
50.         l_result.remove(max(l_result))
    
51.         findNums(l_pr, l_primes, 5, l_result)
    
52.     print(l_result)
    
53. if __name__ == '__main__':
    
54.     start = time()
    
55.     euler060()
    
56.     print('cost %.6f sec' % (time() - start))

复制代码

[13, 5197, 5701, 6733, 8389]
cost 10.425042 sec