求素新篇

介绍Python 中的单行求素:

[p for p in range(2,100) if  0 not in [p%d for d in range(2,p-1)]]

问

Her0 <[email protected]>
reply-to        [email protected]
to      python-cn`CPyUG`华蟒用户组 <[email protected]>
date    Sat, Jul 19, 2008 at 17:39
subject [CPyUG:59701] 求0~100之间的所有素数 大家可能都做过。请对一下几个方法给出你的评价！

  1 #coding:utf-8
  2 '''cdays-5-exercise-3.py 求0~100之间的所有素数
  3     @note: for循环, 列表类型
  4     @see: math模块使用可参考http://docs.python.org/lib/module-math.html
  5 '''
  6
  7 from math import sqrt
  8
  9 N = 100
 10 #基本的方法
 11 result1 = []
 12 for num in range(2, N):
 13     f = True
 14     for snu in range(2, int(sqrt(num))+1):
 15         if num % snu == 0:
 16            f = False
 17            break
 18     if f:
 19         result1.append(num)
 20 print result1
 21
 22 #更好的方法
 23 result2 = [ p for p in range(2, N) if 0 not in [ p% d for d in
range(2, int(sqrt(p))+1)] ]
 24 print result2

新功能

subowen <[email protected]>
reply-to        [email protected]
to      [email protected]
date    Sat, Jul 19, 2008 at 23:34
subject [CPyUG:59739] Re: 求0~100之间的所有素数 大家可能都做过。请对一下几个方法给出你的评价！

时代总要进步的 老皇历也要改进

• 2.5 的新函数 all 和any + generator 不论从语义还是速度上都是巨大的进步

python -mtimeit "[p for p in range(2,100) if  0 not in [p%d for d in range(2,p-1)]]"
  1000 loops, best of 3: 1.17 msec per loop
python -mtimeit "[p for p in range(2,100) if all( p%d for d in range(2,p//2))]"
  1000 loops, best of 3: 477 usec per loop
python -mtimeit "[p for p in range(2,1000) if  0 not in [p%d for d in range(2,p-1)]]"
  10 loops, best of 3: 95 msec per loop
python -mtimeit "[p for p in range(2,1000) if all( p%d for d in range(2,p//2))]"
  100 loops, best of 3: 15.2 msec per loop

• 2.5 的新函数 all 和any + generator 不论从语义还是速度上都是巨大的进步

再来个邪恶的:)

python -mtimeit "reduce(lambda l,y: all(y % x for x in l[:len(l)//2])and l+[y] or l,xrange(2,100),[] )"
  1000 loops, best of 3: 386 usec per loop

python -mtimeit "reduce(lambda l,y: all(y % x for x in l[:len(l)//2])and l+[y] or l,xrange(2,1000),[] )"
  100 loops, best of 3: 5.61 msec per loop

-- 知止而后有定，定而后能静，静而后能安，安而后能虑，虑而后能得。

继续优化

yuting cui <[email protected]>
reply-to        [email protected]
to      [email protected]
date    Sun, Jul 20, 2008 at 02:32

呵呵，再发个继续优化的版本

   1 def getprimes(n):
   2    if n <=2:
   3        return []
   4    if n == 3:
   5        return [2]
   6    u=n**0.5
   7    r=n//2 - 1
   8    l=range(3,n,2)
   9    c=3
  10    t=0
  11    s=3
  12    while c < u:
  13        if l[t]:
  14            for i in xrange(s,r,c):
  15                l[i]=0
  16        s+=(c<<1)+2
  17        c+=2
  18        t+=1
  19    return [2]+[e for e in l if e]

反馈

创建 by -- ZoomQuiet [2008-07-20 04:40:01]