Python素数Eratosthenes的筛子

发布时间：2020-12-20 13:02:27 所属栏目：Python 来源：网络整理

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

嗨,有谁能告诉我如何在这段代码中实现Eratosthenes筛选以使其快速？如果你能用筛子完成它,将非常感谢帮助.在这个特定的代码中,我真的遇到了麻烦.

#!/usr/bin/env python
import sys

T=10 #no of test cases
t=open(sys.argv[1],'r').readlines()

import math
def 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 case
a=[1,4,7,10,13,16,19,22,25,28]
count=0
for 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:
                            pass

print "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):

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!