计算区间内素数的算法不起作用

Question

我正在尝试提出一种算法，该算法可以找到从起始数到结束数的所有素数，而无需从 2 开始并使用 Eratosthenes 筛法计算到结束数的所有素数并删除间隔我想。而不是暴力破解间隔中的每个数字。

我在 python 中修改了埃拉托色尼筛法的现有符号。这是我到目前为止得到的：

def m(n: int, l: list):
    for i, v in enumerate(l):
        if v % n == 0 and v != n and v != False:
            break
    for v in range(i, len(l), n):
        l[v] = False
    return l

这个函数可以把数组l中一个数n的所有公倍数都设置为false，和埃拉托色尼筛法标记非素数的原理一样。这是调用函数的方式：

l = list(range(10, 20))
for i in range(2, 20):
    m(i, l)
print(l)

在此配置中，程序计算从 10 到（排除）20 的所有素数。

输出如下所示：

[False, 11, False, 13, False, False, False, 17, False, False]

但它应该是这样的：

[False, 11, False, 13, False, False, False, 17, False, 19]

数组的最后一个质数似乎被忽略了。当我试图计算从 10 到（排除）21 时，它检测到 19 是质数。

我做错了什么？

Answer 1

对于您的特定用例，19 被 False 覆盖。在第二个循环开始之前，我添加了一些回退/完整性检查。您可以通过我的 print 日志查看发生了什么：

def m(n: int, l: list):
    # set i to its max value
    broke_out = False
    for i, v in enumerate(l):
        if v % n == 0 and v != n and v != False:
            print(f"breaking on index :{i}")
            broke_out = True
            break
    # SANITY CHECK: if we never broke out of the above loop and we're on the last index, we're done.
    if not broke_out and i == len(l)-1:
        return l
    # now use i as the starting point in this loop
    for x in range(i, len(l), n):
        # if not isinstance(x, int):
        print(f"about to overwrite l[x] which is: {l[x]} where x is: {x}")
        # if l[x] % n == 0:
        l[x] = False
    print(f"State of l before returning : {l}")
    return l

l = list(range(10, 20))

for i in range(2, 20):
    m(i, l)

print(l)

完整输出：

breaking on index :0
about to overwrite l[x] which is: 10 where x is: 0
about to overwrite l[x] which is: 12 where x is: 2
about to overwrite l[x] which is: 14 where x is: 4
about to overwrite l[x] which is: 16 where x is: 6
about to overwrite l[x] which is: 18 where x is: 8
State of l before returning : [False, 11, False, 13, False, 15, False, 17, False, 19]
breaking on index :5
about to overwrite l[x] which is: 15 where x is: 5
about to overwrite l[x] which is: False where x is: 8
State of l before returning : [False, 11, False, 13, False, False, False, 17, False, 19]
[False, 11, False, 13, False, False, False, 17, False, 19]
[Finished in 0.1s]

计算区间内素数的算法不起作用

Algorithm for calculating primes in an interval not working

python

primes

sieve-of-eratosthenes