python - 埃拉托色尼分段筛 : sieving composite numbers by their indexes?

Question

我正在尝试编写一个素数查找器来打印两个给定值之间的素数。我对传统的 sieve 编码没有任何问题，但是当它进行分段时，我的 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 标记为 False，而最后的索引号仅为 10?如果筛子的起始索引号为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 显示的结果匹配.