鱼C论坛Python精英挑战赛（第三季05期）

jerryxjr1220

第三届鱼C论坛精英挑战赛开赛咯！为了增加趣味性，本届比赛增加了“新玩法”-- “押宝玩法”，“竞猜玩法”和“擂主玩法”。

规则：

1. 押宝玩法：进入“押宝”竞猜帖，购买主题（5鱼币）参与“押宝”，最终“押宝”获胜者将平分奖池的奖金并额外获取10鱼币奖励。猜错者将不返还“押宝”的鱼币。若本届比赛无人“押宝”成功，奖金将累计到下次比赛。

2. 竞猜玩法：直接在比赛帖的下方进行投票，凡事“竞赛”获胜者，将奖励5鱼币。竞猜无门槛，人人都可以参与。竞猜以后，请在本帖留个言，方便领取奖励。

3. 擂主玩法：上一期挑战成功的鱼油成为挑战赛的擂主，擂主有优先权提议下一期的赛题，一届挑战赛共分5期，同一届中当擂主最长的鱼油有额外奖励。

本期擂主：无

本期赛题的题型：算法题

由于上期题目偏难，这期降低难度。

题目：完美质数

素数又称质数。指一个大于1的自然数，除了1和此整数自身外，不能被其他自然数整除的数。

我们定义：如果一个素数是完美的素数，当且仅当它是由两个或两个以上的质数拼接而成的。

例如，23是质数，同时2和3也都是质数，所以23就是完美质数；而29是由2和9拼接而成的，但是9不是质数，所以29不是完美质数; 而293可以由29和3构成，29和3都是质数，所以293也是完美质数。

特别地，如果质数中间包含0，0可以忽略。即307可以看作由3和7构成，忽略0。

已知：1000以内的完美质数有“23 37 53 73 113 137 173 193 197 211 223 227 229 233 241 257 271 277 283 293 307 311 313 317 331 337 347 353 359 367 373 379 383 389 397 433 503 523 541 547 557 571 577 593 613 617 673 677 719 727 733 743 757 761 773 797 977”总和是 23419。

求1亿（10**8）以内所有完美质数的和。

def sum_perfect_primes(limit):
    "Your code here"
    return the_sum_of_the_perfect_primes_within_the_limit


要求：

程序运算正确，执行效率最高的即为获胜者。

竞猜：
正确答题的参赛者的人数是奇数还是偶数？

比赛截止日期：10月8日24时，竞猜和押宝截止日期为10月7日

由于国庆假期，故延长3天！

国庆节快乐！

@小甲鱼 @冬雪雪冬 @～风介～ @SixPy

ttyhtg

我猜是奇数

C4rB0n

精英赛的题目感觉有点不明白，定义：完美素数是由两个或两个以上的质数拼接而成，而29是质数，那为什么含有29的三位数的质数不能是完美素数？

银色的色

@冬雪雪冬

gunjang

正在赶工。。。
发现227是2 2 7组成的，本身也是素数，但是却不在示例的1000内完美素数表内
同理227 257 277 557 727 757

jerryxjr1220

gunjang 发表于 2017-10-7 23:15
正在赶工。。。
发现227是2 2 7组成的，本身也是素数，但是却不在示例的1000内完美素数表内
同理227 257  ...

227应该算的，可能我的程序也有点问题，漏掉了。

gunjang

#122975378089761
运行10分钟，不知道对不对，应该还有优化的空间

1. #http://bbs.fishc.com/forum.php?mod=viewthread&tid=97298
   
2. from math import sqrt
   
3. import time
   
4. 
   
5. st = time.time()
   
6. p10bindex = [0]
   
7. 
   
8. def generateprime10b():
   
9.         r =[2, 3, 5, 7]
   
10.         currbit = 10
    
11.         for i in range(12, 10**7, 6): #10^7
    
12.                 i1 = i - 1
    
13.                 si = int(sqrt(i1))
    
14.                 for p in r:
    
15.                         if (p > si) or (i1 % p) == 0:
    
16.                                 break
    
17.                 if i1 % p != 0:
    
18.                         r.append(i1)
    
19.                         if i1 > currbit:
    
20.                                 p10bindex.append(len(r)-1)
    
21.                                 currbit *= 10
    
22. 
    
23.                 i1 = i + 1
    
24.                 si = int(sqrt(i1))
    
25.                 for p in r:
    
26.                         if (p > si) or (i1 % p) == 0:
    
27.                                 break
    
28.                 if i1 % p != 0:
    
29.                         r.append(i1)
    
30.                         if i1 > currbit:
    
31.                                 p10bindex.append(len(r)-1)
    
32.                                 currbit *= 10
    
33. 
    
34.         p10bindex.append(len(r))                       
    
35.         return r
    
36. 
    
37. def isPrime(n):
    
38.         if n < 10**7:
    
39.                 st = 0
    
40.                 ed = len(primes10b)-1
    
41.                 while st <= ed:
    
42.                         mid = (st+ed)//2
    
43.                         if primes10b[mid] > n:
    
44.                                 ed = mid -1
    
45.                         elif primes10b[mid] < n:
    
46.                                 st = mid + 1
    
47.                         else:
    
48.                                 return True
    
49.                 return False
    
50.         sn = int(sqrt(n))
    
51.         for p in primes10b:
    
52.                 if p > sn:
    
53.                         return True
    
54.                 if n%p == 0:
    
55.                         return False
    
56. 
    
57. def genPerfectPrimes():
    
58.         rsum = 0
    
59.         pplist = [primes10b[:p10bindex[1]]] #one digit primes
    
60.         for digitno in range(2, 8+1): #8+1
    
61.                 r = []
    
62.                 currpplist = []
    
63.                 for currdigitno in range(1, digitno):
    
64.                         currlist = pplist[currdigitno-1]
    
65.                         for nextdigitno in range(1, digitno-currdigitno+1):
    
66.                                 nextlist = pplist[nextdigitno-1]
    
67.                                 currmul = 10**(digitno-currdigitno)
    
68.                                 for nt in nextlist:
    
69.                                         if (nt%5 == 0) or (nt%2 == 0):
    
70.                                                 continue
    
71.                                         for curr in currlist:
    
72.                                                 num = curr * currmul + nt
    
73.                                                 if isPrime(num):
    
74.                                                         r.append(num)
    
75.                                                 if digitno != 8:
    
76.                                                         currpplist.append(num)
    
77.                 if digitno != 8:
    
78.                         currpplist.extend(primes10b[p10bindex[digitno-1]:p10bindex[digitno]])
    
79.                         currpplist = list(set(currpplist)) #remove Duplicate
    
80.                         pplist.append(currpplist)
    
81.                 rsum += sum(set(r))
    
82.                 print('cost %ss' %(time.time()-st))
    
83.                 print('DigitNo=%d Sum=%d' %(digitno, rsum))
    
84.                 print('count of Perfect Primes: %d'%(len(currpplist)))
    
85. 
    
86.         return rsum
    
87. 
    
88. primes10b = generateprime10b() #21s
    
89. print('generate primes(<10billion) cost %ss' %(time.time()-st))
    
90. r = genPerfectPrimes()
    
91. print(r) #122975378089761
    
92. #digitno=7 ,sum is 1373257989644,cost 149s
    
93. print(time.time()-st) #545s

复制代码

gunjang

gunjang 发表于 2017-10-8 12:32
#122975378089761
运行10分钟，不知道对不对，应该还有优化的空间

抱歉没发现有8221，重新导出4位数的pp
@jerryxjr1220

1. pp4 = [2053, 4111, 6173, 4127, 4129, 2083, 4133, 2089, 8233, 8237, 6197, 4153, 4157, 4159, 2113, 4177, 8273, 2131, 2137, 8293, 8297, 8311, 4217, 8317, 2179, 8329, 2203, 2207, 8353, 2213, 6317, 8377, 2237, 2239, 2243, 8389, 2251, 2267, 2269, 2273, 4327, 2281, 4337, 2293, 2297, 4357, 2311, 4373, 2333, 2341, 2347, 4397, 2357, 2371, 2377, 6473, 2383, 2389, 2393, 8537, 2417, 8573, 2437, 4493, 8597, 2467, 2473, 2477, 2503, 2521, 2531, 2543, 2557, 2579, 4637, 2593, 6703, 2617, 6719, 4673, 2633, 6733, 6737, 2647, 4703, 2659, 6761, 4723, 2677, 4729, 2683, 6779, 4733, 2693, 8837, 2707, 2711, 4759, 2713, 2719, 2729, 2731, 4783, 6833, 2741, 4789, 4793, 2753, 2767, 2777, 8923, 8929, 2789, 8933, 2797, 8941, 6917, 8971, 4877, 2833, 2837, 2857, 2887, 2897, 2903, 7013, 2917, 7019, 2927, 7027, 4993, 7043, 2953, 5003, 2957, 7057, 5011, 2971, 5023, 7079, 7103, 3011, 5059, 7109, 3019, 3023, 5077, 7127, 7129, 3037, 3041, 5101, 7151, 5107, 3061, 1013, 7159, 5113, 3067, 3079, 7177, 1033, 3083, 3089, 7193, 3109, 7207, 7211, 7213, 5167, 3119, 7219, 5179, 7229, 3137, 7237, 1093, 1097, 7243, 5197, 9293, 7247, 1103, 7253, 3163, 1117, 3167, 1123, 1129, 5227, 3181, 5231, 5233, 7283, 5237, 3191, 7297, 1153, 3203, 7307, 5261, 3217, 1171, 5273, 3229, 5279, 5281, 9377, 7331, 7333, 5297, 3251, 3253, 7349, 5303, 3257, 3259, 9413, 3271, 5323, 5333, 7393, 5347, 3307, 3313, 3319, 7417, 3323, 1277, 3329, 9473, 3331, 7433, 3343, 3347, 1303, 1307, 3359, 3361, 7457, 5413, 1319, 5417, 3371, 5419, 3373, 1327, 7477, 5431, 3389, 5437, 7487, 9533, 5443, 5449, 7499, 1361, 7507, 3413, 1367, 7517, 1373, 7523, 5477, 5479, 7529, 3433, 7537, 7541, 3449, 7547, 5503, 3457, 5507, 3461, 7559, 3463, 7561, 3467, 5519, 5521, 7573, 5527, 7577, 5531, 7583, 3491, 7589, 3499, 5557, 7607, 3511, 5563, 3517, 5569, 5573, 3527, 3529, 3533, 9677, 3541, 1493, 3547, 7643, 3557, 3559, 3571, 9719, 7673, 3583, 9733, 3593, 5641, 7691, 5647, 9743, 5653, 3607, 7703, 5659, 3613, 3617, 7717, 9767, 7723, 3631, 7727, 5683, 3643, 7741, 5693, 5701, 7753, 3659, 7757, 5711, 7759, 5717, 3673, 3677, 1637, 5737, 9833, 3691, 5741, 7789, 5743, 7793, 3701, 3709, 3719, 3727, 7823, 5779, 3733, 7829, 5783, 3739, 7853, 3761, 3767, 3769, 1723, 5821, 7873, 3779, 5827, 7877, 1733, 7883, 1741, 5839, 3793, 1747, 3797, 1753, 1759, 5857, 7907, 3821, 3823, 7919, 1777, 9973, 7927, 1783, 3833, 5881, 7933, 1789, 7937, 5897, 3853, 5903, 3863, 5923, 3877, 5927, 3881, 5953, 3907, 3911, 3919, 3929, 3947, 1907, 1913, 3967, 1931, 1933, 8093, 4013, 1973, 8117, 6073, 1979, 1993, 1997, 2003, 2011, 2017, 6113, 2027, 2029, 6131, 6133, 4093, 6143]
   
2. is_prime = lambda n: True if n in {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67} else all(False for p in {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67} if pow(p,n-1,n) != 1)
   
3. print(len(pp4), sum(pp4)) #428 2034048
   
4. for p in pp4:
   
5.         if not is_prime(p):
   
6.                 print(p)
   
7. #23419+2034048=2057467

复制代码

结果显示都是prime呀