在一个范围内打印质数。埃拉托什尼筛

Question

我把从x到y（包括x）的所有数字都加到了列表1中。我现在只需要列表只包含从x到y的质数

def primes(x , y):
    list1 = []
    for i in range(m, n + 1):
            list1.append(i)
    for elements in list1:
            if elements % 2 == 0:
                    pos = list1.index(elements)
                    list1.pop(pos)
    return list1

我把从x到y（包括x）的所有数字都加到了列表1中，也去掉了偶数，但我似乎无法去掉其他不是质数的数字。我现在只需要列表只包含从x到y的质数

例如x=7，y=23

列表1=[7，11，13，17，19，23]

提前谢谢

Answer 1

这里有一些提示：您不需要生成x和y之间的整数的整个列表，然后删除非素数的那个。一种更快的方法是生成所有小于y的素数，然后删除那些小于x的素数。这样你就可以使用先前计算出的质数来有效地检查一个数是否是质数。在

所以让我们从头开始。2是唯一的偶数素数。所以你可以从2开始迭代奇数直到y。如果一个数不能被任何前一个素数整除，它就是素数。在

对于0到y之间的每一个数，首先假设它是质数。检查它是否可以被前面的素数整除。如果它是任何质数的倍数，那么您可以停止（break），因为您知道它不是质数。如果它不是任何先前素数的倍数，则将其添加到素数列表中。在

最后，一旦您有了介于0和y之间的素数列表，就可以删除小于x的元素。在

在Python中给出：

def primes(x , y):
    l = [2] # list of prime numbers
    for n in range(3,y+1,2): # iterations over odd numbers
        isprime = True
        for e in l:
            if n % e == 0:
                isprime = False
                break
        if(isprime):
            l.append(n)

    return [e for e in l if e >= x]

print(primes(7,23))
# [7, 11, 13, 17, 19, 23]