鱼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多秒：

import numpy as np 
def sum_perfect_primes(limit):
   def is_perfect(n):
      n = str(n)
      if len(n)<2: return False
      for i in range(len(n)-1,0,-1):
         if primes[int(n[:i])] and n[i:]: 
                 if primes[int(n[i:])]:
                         return True  
                 else:
                         if is_perfect(n[i:]): 
                                 return True

   primes = np.ones(limit, dtype=np.bool)
   for i in range(2,int(limit**0.5+1)):
      if primes[i]: primes[i*i::i] = False
   primes[0], primes[1] = False, False
   plist = np.nonzero(primes)[0][2:]
   c = 0
   for p in plist:
      if is_perfect(p):
 #        print(p, end=' ')
         c += p
   return c
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,估计这就是解释型语言和编译语言的差距，百倍

#http://bbs.fishc.com/forum.php?mod=viewthread&tid=97298
import time
import numpy as np

st = time.time()

def genPerfectPrimes():
        primes = np.ones(10**8, dtype=np.bool)
        for i in range(2, int((10**8)**0.5)+1):
                if primes[i]: primes[i*i::i] = False
        primes[0], primes[1] = False, False
        print('generate primes(<10billion) cost %ss' %(time.time()-st)) #2.8s

        combprimes = primes.copy() # one or more primes
        pprimes = np.zeros(10**8, dtype=np.bool)

        cplist = [[] for i in range(9)]
        cplist[1] = [2,3,5,7]
        for digitno in range(2, 8+1): 
                t1 = time.time()
                for currdigitno in range(1, digitno):
                        currlist = cplist[currdigitno]
                        for nextdigitno in range(1, digitno-currdigitno+1):
                                nextlist = cplist[nextdigitno]
                                currmul = 10**(digitno-currdigitno)
                                for curr in currlist:
                                        curr *= currmul
                                        for nt in nextlist:
                                                num = curr + nt
                                                combprimes[num] = True
                                                if primes[num]:
                                                        pprimes[num] = True
                if digitno != 8:
                        cplist[digitno] = np.nonzero(combprimes[10**(digitno-1):10**digitno])[0]+10**(digitno-1)
                
                print('DigitNo=%d cost %ss' %(digitno, time.time()-t1))#8 cost 57s
        t1 = time.time()
        r = np.nonzero(pprimes)[0].astype(np.int64).sum() #must astype, use sum(...) may #overflow encountered in int_scalars 
        print('calculte sum cost %ss' %(time.time()-t1)) #13s

        return r

#23419 when <10000
print(genPerfectPrimes()) #122975378089761 count is 2409775
print(time.time()-st) #545s => 61s