3

嗨，谁能告诉我如何在这段代码中实现埃拉托色尼筛法以使其快速运行？如果您能用筛子完成它，我们将不胜感激。在这个特定的代码中，我真的很难做到这一点。

#!/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
4

6 回答 6

12

在 Python 中加速筛子的一个老技巧是使用花哨的 ;-) 列表切片符号，如下所示。这使用 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, 7, 11, 13, 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):
于 2013-10-14T00:49:58.090 回答
10

此处发布的原始海报和其他解决方案都犯了同样的错误；如果您使用模运算符或任何形式的除法，您的算法是试除法，而不是Eratosthenes 的筛法，并且会慢得多，O(n^2) 而不是 O(n log log n)。这是一个简单的 Python 埃拉托色尼筛法：

def primes(n): # sieve of eratosthenes
    ps, sieve = [], [True] * (n + 1)
    for p in range(2, n + 1):
        if sieve[p]:
           ps.append(p)
           for i in range(p * p, n + 1, p):
               sieve[i] = False
    return ps

这应该会在不到一秒的时间内找到所有小于一百万的素数。如果你对使用素数编程感兴趣，我在我的博客上谦虚地推荐这篇文章。

于 2013-10-13T14:28:13.323 回答
1

我能想到的最快的实现

def sieve(maxNum):
    yield 2
    D, q = {}, 3
    while q <= maxNum:
        p = D.pop(q, 0)
        if p:
            x = q + p
            while x in D: x += p
            D[x] = p
        else:
            yield q
            D[q*q] = 2*q
        q += 2
    raise StopIteration

资料来源：http ://code.activestate.com/recipes/117119-sieve-of-eratosthenes/#c4

更换这部分

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

和

primes = [prime for prime in sieve(10000000)]
def is_prime(n):
    return n in primes

而不是10000000你可以放任何你需要素数的最大数字。

于 2013-10-13T13:10:58.177 回答
0

这是一个非常快速的生成器，减少了内存使用。

def pgen(maxnum): # Sieve of Eratosthenes generator
    yield 2
    np_f = {}
    for q in xrange(3, maxnum + 1, 2):
        f = np_f.pop(q, None)
        if f:
            while f != np_f.setdefault(q+f, f):
                q += f
        else:
            yield q
            np = q*q
            if np < maxnum:  # does not add to dict beyond maxnum
                np_f[np] = q+q

def is_prime(n):
    return n in pgen(n)

>>> is_prime(541)
True
>>> is_prime(539)
False
>>> 83 in pgen(100)
True
>>> list(pgen(100)) # List prime numbers less than or equal to 100
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
89, 97]
于 2013-10-16T20:17:47.470 回答
0

这是一个简单的生成器，仅使用不预分配内存的添加。筛子的大小与素数字典一样大，内存使用量仅根据需要增长。

def pgen(maxnum): # Sieve of Eratosthenes generator
    pnext, ps = 2, {}
    while pnext <= maxnum:
        for p in ps:
            while ps[p] < pnext:
                ps[p] += p
            if ps[p] == pnext:
                break
        else:
            ps[pnext] = pnext
            yield pnext
        pnext += 1

def is_prime(n):
    return n in pgen(n)

>>> is_prime(117)
>>> is_prime(117)
False
>>> 83 in pgen(83)
True
>>> list(pgen(100)) # List prime numbers less than or equal to 100
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
89, 97]
于 2013-10-16T21:22:48.573 回答
0

这是一个简单的集合解决方案。与许多列表算法相比，这非常快。由于哈希表，使用集合进行计算要快得多。（是什么让集合比 Python 中的列表更快？）

问候

----------------------------------
from math import *

def sievePrimes(n):

    numbers = set()
    numbers2 = set()
    bound = round(sqrt(n))

    for a in range(2, n+1):
        numbers.add(a)

    for i in range(2, n):
        for b in range(1, bound):
            if (i*(b+1)) in numbers2:
                continue
            numbers2.add(i*(b+1))
    numbers = numbers - numbers2

    print(sorted(numbers))

简单的解决方案

于 2016-01-20T20:47:05.517 回答