Python素数Eratosthenes的筛子

概述嗨,有谁能告诉我如何在这段代码中实现Eratosthenes筛选以使其快速？如果你能用筛子完成它,将非常感谢帮助.在这个特定的代码中,我真的遇到了麻烦. #!/usr/bin/env pythonimport sysT=10 #no of test casest=open(sys.argv[1],'r').readlines()import mathdef is_prime(n): 嗨,有谁能告诉我如何在这段代码中实现Eratosthenes筛选以使其快速？如果你能用筛子完成它,将非常感谢帮助.在这个特定的代码中,我真的遇到了麻烦.

#!/usr/bin/env pythonimport sysT=10 #no of test casest=open(sys.argv[1],'r').readlines()import mathdef is_prime(n):    if n == 2:        return True    if n%2 == 0 or n <= 1:        return False    sqr = int(math.sqrt(n)) + 1    for divisor in range(3,sqr,2):        if n%divisor == 0:            return False    return True#first line of each test casea=[1,4,7,10,13,16,19,22,25,28]count=0for i in a:    b=t[i].split(" ")    c=b[1].split("\n")[0]    b=b[0]    for k in xrange(int(b)):        d=t[i+1].split(" ")        e=t[i+2].split(" ")        for g in d:            for j in e:                try:                    sum=int(g)+int(j)                    p=is_prime(sum)                             if p==True:                        count+=1                        print count                    else:                        pass                except:                    try:                        g=g.strip("\n")                        sum=int(g)+int(j)                        p=is_prime(sum)                        if p==True:                            count+=1                            print count                        else:                            pass                    except:                        j=j.strip("\n")                        sum=int(g)+int(j)                        p=is_prime(sum)                        if p==True:                            count+=1                            print count                        else:                            passprint "Final count"+count

解决方法 在Python中加速筛分的一个老技巧是使用花式;-) List slice表示法,如下所示.这使用Python 3.注释中注明了Python 2所需的更改：

def sIEve(n):    "Return all primes <= n."    np1 = n + 1    s = List(range(np1)) # leave off `List()` in Python 2    s[1] = 0    sqrtn = int(round(n**0.5))    for i in range(2,sqrtn + 1): # use `xrange()` in Python 2        if s[i]:            # next line:  use `xrange()` in Python 2            s[i*i: np1: i] = [0] * len(range(i*i,np1,i))    return filter(None,s)

在Python 2中,它返回一个列表;在Python 3中是一个迭代器.这里是Python 3：

>>> List(sIEve(20))[2,3,5,11,17,19]>>> len(List(sIEve(1000000)))78498

这两个都在眨眼间.鉴于此,以下是如何构建is_prime函数：

primes = set(sIEve(the_max_integer_you_care_about))def is_prime(n):    return n in primes

它是set()的一部分,使它变得快速.当然功能很简单你可能想写：

if n in primes:

直接而不是搞乱：

if is_prime(n):

总结

以上是内存溢出为你收集整理的Python素数Eratosthenes的筛子全部内容，希望文章能够帮你解决Python素数Eratosthenes的筛子所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。