埃拉托斯特尼筛法：通过索引筛选合成数？

Question

我正在尝试编写一个程序，用来找出两个给定值之间的质数。我对传统的筛法没有问题，但在分段筛法上，我的Python知识有些不足。以下是我目前的进展：

def primes(n): # traditional sieve finding primes up to sqrt(n)
    myPrimeList= []
    mySieve= array('B', [True]) * (int(n**0.5)+1)
    for i in range(2,int((n**0.5)+1)):
        if mySieve[i]:
            myPrimeList.append(i)
            for x in range(i*i,int(n**0.5)+1,i):
                mySieve[x]= False
    return myPrimeList

def rangedprimes(x,y):
    output = []
    sieve = [True] * (y-x+1)
    primeList = primes(y) # primes up to sqrt(y)
    minimums = [(x//m)*m for m in primeList if x>=m] # multiplying primes so they get close to the lower limit
    zipped = list(zip(primeList, minimums)) # just zipped to see it clearer, contributes nothing
    return zipped

print(primes(20))
print(rangedprimes(10,20))

[2, 3] # primes up to sqrt(20)
[(2, 10), (3, 9)] # primes and their smallest multiples

根据算法，我需要把这些数字 [10, 12, 14, 15, 16, 18, 20] 在筛子中从 True 改成 False，这样剩下的标记为 True 的数字才能是质数。现在我遇到问题了，因为我的筛子里只有 True 的数量是 y-x+1，这意味着它的索引范围是从 0 到 y-x。举个例子，像 16 或 20 这样的数字，怎么能在一个最后索引只有 10 的筛子里标记为 False 呢？如果筛子的起始索引是 10，最后的索引是 20，我就可以通过查看它们的索引来找到这些数字，并把它们标记为 False。

在这种情况下，筛子和范围内的合成数之间应该是什么关系呢？

Answer 1

我觉得你想做的事情是这样的：

import math

def prime_sieve(n):
    """Use the Sieve of Eratosthenes to list primes 0 to n."""
    primes = range(n+1)
    primes[1] = 0
    for i in range(4, n+1, 2):
        primes[i] = 0
    for x in range(3, int(math.sqrt(n))+1, 2):
        if primes[x]:
            for i in range(2*primes[x], n+1, primes[x]):
                primes[i] = 0
    return filter(None, primes)

def ranged_primes(x, y):
    """List primes between x and y."""
    primes = prime_sieve(int(math.sqrt(y)))
    return [n for n in range(x, y) if all(n % p for p in primes)]

注意，我一直使用传统的筛法一直到 n，然后在 ranged_primes 函数中调用它来处理 sqrt(y)。

这是一个从 10**6 到 10*6 + 10**3 的示例：

>>> ranged_primes(10**6, 10**6+10**3)
[1000003, 1000033, 1000037, 1000039, 1000081, 
 1000099, 1000117, 1000121, 1000133, 1000151, 
 1000159, 1000171, 1000183, 1000187, 1000193, 
 1000199, 1000211, 1000213, 1000231, 1000249, ...]

这个结果和 Wolfram Alpha 显示的结果是一样的。