埃拉托斯滕的分段筛分：用它们的指数筛选复合数？

Question

我正在尝试编写一个素数查找器，它可以在两个给定值之间打印素数。我对编写传统的siever没有任何问题，但是当它被分段时，我的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次的筛子，这意味着它有从0到{}的索引。例如，在最后一个索引号将仅为10的筛子中，如何用^{标记16或20？如果sieve的起始索引号是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)]

{{{cd2}保持传统的

从10**6到{}的演示：

^{pr2}$

匹配Wolfram Alpha显示的结果。在