Python：每日一题 205

喜欢吃菠菜

凌九霄 发表于 2018-10-17 09:38
首先这个方式确实简洁，效率大概是我那个的2倍多点。我相信，随着范围的增大，速度的优势也会更大。缺 ...

#筛选法求素数
    def getprimes(n):
        l=[1,1,1]+[i%2 for i in range(3,n+1)]
        i=3
        while i*i<=n:
            if l[i]!=0:
                j=i*i
                while n>=j:
                    l[j]=0
                    j+=2*i
            i+=2
        return [2]+[i for i in range(3,n+1,2) if l[i]!=0]
    import time
    start=time.clock()  
    print(getprimes(10000000))
    print('时间:%f' % (time.clock()-start))  

#这个是加入算法的高效快速的查找方法，1千万内的素数大概只要10秒左右吧，1个亿大概200秒左右吧。参考一下。

考拉熊

过来顶一下

凌九霄

喜欢吃菠菜 发表于 2018-11-6 23:45
#筛选法求素数
    def getprimes(n):
        l=[1,1,1]+

嘿嘿，还真执着啊，自己有运行过么？或者只注意到时间？

sunrise085

这是我写的程序~~不知还能否在压缩运行时间

1. def sieve(num=200):
   
2.         fulllist=list(range(2,num+1))
   
3.         result=[]
   
4.         while fulllist:
   
5.                 result.append(fulllist.pop(0))
   
6.                 for i in fulllist:
   
7.                         if i%result[-1]==0:
   
8.                                 fulllist.remove(i)
   
9.         return result

复制代码

uune

1. n = 200
   
2. num = [i for i in range(2,n)]   #生成2到n之间的数字
   
3. 
   
4. for i in num:       #遍历num列表
   
5.     #因为质数的因数只有1和本身，所以从2开始。最小质数是2，x的最大值是n//2
   
6.     for x in range(2,n//2):
   
7.         if i*x in num:
   
8.             #print(i*x, '在内num列表中')
   
9.             num.remove(i*x)
   
10. print('num =',num)

复制代码