高效查找一定范围内的素数

Question

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

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

Answer 1

我认为以下方法有效：

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]

Answer 2

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

Answer 3

您已经拥有从 2 到 end 的素数，因此您只需过滤返回的列表即可。

Answer 4

一种方法是使用 end = top 运行筛分代码，并修改最后一行，只给出大于bottom的数字：

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

从底部开始并迭代奇数，检查它们是否是质数。您需要一个 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