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

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/em>?如果筛子的起始索引号是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 显示的结果.