2

这是我为 python3 的 Eratosthenes 筛子找到的算法代码。我想要做的是编辑它，以便我可以输入一个底部和顶部的范围，然后输入一个素数列表直到底部一个，它将输出该范围内的素数列表。但是，我不太确定该怎么做。如果您能提供帮助，将不胜感激。

from math import sqrt
def sieve(end):  
    if end < 2: return []  

    #The array doesn't need to include even numbers  
    lng = ((end//2)-1+end%2)  

    # Create array and assume all numbers in array are prime  
    sieve = [True]*(lng+1)  

    # In the following code, you're going to see some funky  
    # bit shifting and stuff, this is just transforming i and j  
    # so that they represent the proper elements in the array.  
    # The transforming is not optimal, and the number of  
    # operations involved can be reduced.  

    # Only go up to square root of the end  
    for i in range(int(sqrt(end)) >> 1):  

        # Skip numbers that aren’t marked as prime  
        if not sieve[i]: continue  

        # Unmark all multiples of i, starting at i**2  
        for j in range( (i*(i + 3) << 1) + 3, lng, (i << 1) + 3):  
            sieve[j] = False  

    # Don't forget 2!  
    primes = [2]  

    # Gather all the primes into a list, leaving out the composite numbers  
    primes.extend([(i << 1) + 3 for i in range(lng) if sieve[i]])  

    return primes
4

4 回答 4

2

我认为以下是有效的：

def extend_erathostene(A, B, prime_up_to_A):
    sieve = [ True ]* (B-A)
    for p in prime_up_to_A:
        # first multiple of p greater than A
        m0 = ((A+p-1)/p)*p
        for m in range( m0, B, p):
            sieve[m-A] = False
    limit = int(ceil(sqrt(B)))
    for p in range(A,limit+1):
        if sieve[p-A]:
            for m in range(p*2, B, p):
                sieve[m-A] = False 
    return prime_up_to_A + [ A+c for (c, isprime) in enumerate(sieve) if isprime]
于 2011-06-23T23:37:42.607 回答
2

这个问题被称为“埃拉托色尼的分段筛”。谷歌提供了几个有用的参考资料。

于 2011-06-24T13:38:43.960 回答
0

你已经有了从 2 到 的素数end，所以你只需要过滤返回的列表。

于 2011-06-23T22:42:30.483 回答
0

一种方法是运行筛代码end = top并修改最后一行以仅提供大于底部的数字：

如果范围与其大小相比较小（即顶部与底部相比较小），那么您最好使用不同的算法：

从底部开始遍历奇数，检查它们是否为素数。你需要一个 isprime(n) 函数，它只检查 n 是否可以被从 1 到 sqrt(n) 的所有奇数整除：

def isprime(n):
    i=2
    while (i*i<=n):
        if n%i==0: return False
        i+=1
    return True
于 2011-06-23T22:45:05.800 回答