男单 618

生活象筒装的卫生纸,开始的时候怎么扯都不觉得在转,后来转的越来越快。

筛法求素数表

with 2 comments

第一个版本:

P=range(2,20001)
i=0
l=len(P)
t1=datetime.datetime.now()
while i
    for item in P[(i+1):]:
        if item % P[i]==0:
            P.remove(item)
            l-=1
    i+=1
t2=datetime.datetime.now()
print t2-t1
print P

第二个版本:

P=range(2,20001)
i=0
l=len(P)
t1=datetime.datetime.now()
while i
    temp=[item for item in P[(i+1):] if item % P[i] != 0]
    P=P[:(i+1)]+temp
    l=len(P)
    i+=1
t2=datetime.datetime.now()
print t2-t1
print P

第三个版本:

temp=range(2,20001)
P=[]
t1=datetime.datetime.now()
while temp!=[]:
    P.append(temp[0])
    temp=[item for item in temp if item % P[-1] != 0]
t2=datetime.datetime.now()
print t2-t1
print P

第一个版本需要7秒多,第二个版本只需要2秒多,第三个版本就只需要1.8秒左右了。

注1:刚开始学Python,正在慢慢体会Python的精神,希望能尽快写出Python风格的程序,而不是用Python语言写Pascal程序。
注2:正是因为刚开始学,所以实际上不止三个版本,但是从7秒多优化到2秒以内,还是很有成就感的。
注3:还是太慢了。

Written by amao

2008/10/03 at 22:22

Posted in python

2 Responses to '筛法求素数表'

Subscribe to comments with RSS or TrackBack to '筛法求素数表'.

  1. 发现一个更快(非常快)的版本:

    def primes(n):
      ""” returns a list of prime numbers from 2 to < n “”"
      if n < 2return []
      if n == 2: return [2]
      # do only odd numbers starting at 3
      s = range(3, n, 2)
      # n**0.5 may be slightly faster than math.sqrt(n)
      mroot = n ** 0.5
      half = len(s)
      i = 0
      m = 3
      while m <= mroot:
        if s[i]:
          j = (m * m – 3)//2
          s[j] = 0
          while j < half:
            s[j] = 0
            j += m
        i = i + 1
        m = 2 * i + 3
      # make exception for 2
      return [2]+[x for x in s if x]

    amao

    14 10 08 at 10:42 下午

  2. 还是换一种语言提升的效率更多

    比如用c语言,生成2000000以内的素数表只用2s不到

    vilinov

    17 10 08 at 2:06 下午

Leave a Reply