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

jerryxjr1220

本期挑战赛只有gunjang答题。

gunjang的程序虽然用时比较长，但是结果正确，评选为最终获胜者！

并且gunjang在本季挑战赛中获胜2场，小剑剑和小锟分别都获胜1场。所以gunjang赢得本季精英挑战赛的最终擂主！额外奖励20荣誉值！

本次挑战赛竞猜获胜的是：
新手·ing
舍生取义
银色的色
Teagle
gunjang
Wesleyz
ttyhtg
fhrv
李白-千年之狐
kkmice
请在本帖回复，领取奖励5鱼币。

本期押宝没有获胜者，奖金10鱼币将累积到下一次押宝竞猜中。

有请@小甲鱼 老师颁奖，总共奖励gunjang 105鱼币和20荣誉值，恭喜gunjang！

鱼C论坛Python精英挑战赛第三季全部结束，感谢大家的参与！

jerryxjr1220

贴一下我的解答，递归方法，差不多30多秒：

1. import numpy as np
   
2. def sum_perfect_primes(limit):
   
3.    def is_perfect(n):
   
4.       n = str(n)
   
5.       if len(n)<2: return False
   
6.       for i in range(len(n)-1,0,-1):
   
7.          if primes[int(n[:i])] and n[i:]:
   
8.                  if primes[int(n[i:])]:
   
9.                          return True  
   
10.                  else:
    
11.                          if is_perfect(n[i:]):
    
12.                                  return True
    
13. 
    
14.    primes = np.ones(limit, dtype=np.bool)
    
15.    for i in range(2,int(limit**0.5+1)):
    
16.       if primes[i]: primes[i*i::i] = False
    
17.    primes[0], primes[1] = False, False
    
18.    plist = np.nonzero(primes)[0][2:]
    
19.    c = 0
    
20.    for p in plist:
    
21.       if is_perfect(p):
    
22. #        print(p, end=' ')
    
23.          c += p
    
24.    return c
    
25. print(sum_perfect_primes(10**8)) #122975378089761

复制代码

Teagle

学习一下

gunjang

jerryxjr1220 发表于 2017-10-11 09:02
贴一下我的解答，递归方法，差不多30多秒：

厉害，筛法生产素数，再判断是否是pp
我的正好倒过来，素数组合成pp

新手·ing

支持支持

银色的色

看看，

小锟

恭喜恭喜

gunjang

@jerryxjr1220
虽然已经评比结束了，但是借鉴兄的素数筛法思路，优化到60s
感觉组合算法还有优化空间，有很多重复~~~
感觉numpy使用的好，优化效率很高，同样的sum，自己迭代13s，python的sum溢出，np.sum只要0.14s,估计这就是解释型语言和编译语言的差距，百倍

1. #http://bbs.fishc.com/forum.php?mod=viewthread&tid=97298
   
2. import time
   
3. import numpy as np
   
4. 
   
5. st = time.time()
   
6. 
   
7. def genPerfectPrimes():
   
8.         primes = np.ones(10**8, dtype=np.bool)
   
9.         for i in range(2, int((10**8)**0.5)+1):
   
10.                 if primes[i]: primes[i*i::i] = False
    
11.         primes[0], primes[1] = False, False
    
12.         print('generate primes(<10billion) cost %ss' %(time.time()-st)) #2.8s
    
13. 
    
14.         combprimes = primes.copy() # one or more primes
    
15.         pprimes = np.zeros(10**8, dtype=np.bool)
    
16. 
    
17.         cplist = [[] for i in range(9)]
    
18.         cplist[1] = [2,3,5,7]
    
19.         for digitno in range(2, 8+1):
    
20.                 t1 = time.time()
    
21.                 for currdigitno in range(1, digitno):
    
22.                         currlist = cplist[currdigitno]
    
23.                         for nextdigitno in range(1, digitno-currdigitno+1):
    
24.                                 nextlist = cplist[nextdigitno]
    
25.                                 currmul = 10**(digitno-currdigitno)
    
26.                                 for curr in currlist:
    
27.                                         curr *= currmul
    
28.                                         for nt in nextlist:
    
29.                                                 num = curr + nt
    
30.                                                 combprimes[num] = True
    
31.                                                 if primes[num]:
    
32.                                                         pprimes[num] = True
    
33.                 if digitno != 8:
    
34.                         cplist[digitno] = np.nonzero(combprimes[10**(digitno-1):10**digitno])[0]+10**(digitno-1)
    
35.                
    
36.                 print('DigitNo=%d cost %ss' %(digitno, time.time()-t1))#8 cost 57s
    
37.         t1 = time.time()
    
38.         r = np.nonzero(pprimes)[0].astype(np.int64).sum() #must astype, use sum(...) may #overflow encountered in int_scalars
    
39.         print('calculte sum cost %ss' %(time.time()-t1)) #13s
    
40. 
    
41.         return r
    
42. 
    
43. #23419 when <10000
    
44. print(genPerfectPrimes()) #122975378089761 count is 2409775
    
45. print(time.time()-st) #545s => 61s
    

复制代码