查找素数的Python函数

Question

这不是关于寻找质数，而是关于如何将代码转换为函数。

所以我有这段代码可以帮助我打印 2-100 之间的素数:

pnumber = [x for x in range(2, 101) if all(x % i for i in range(2, x))]
print(pnumber)

如果我将其定义为一个函数，用于查找某个范围内的素数:

 def p_number(a, b):
     pnumber = [x for x in range(a, b+1) if all(x % i for i in range(2, b))]
     print(pnumber)

 p_number(2, 100)

你可以看到我用 a 代替 2，用 b 代替 100，并相应地更改代码。但不知何故，这行不通，它会输出一个空列表。

我想知道为什么？

Answer 1

请注意，如果您在检查中使用 upperbound b:

all(x % i for i in range(2, b))

这将包括所有小于b的质数。所以 2、3、5 等也是 range(2, b) 的一部分(给定 b 足够大)。所以这意味着如果我们测试 3 是否是质数，我们将检查 i = 3，并且 3 % 3 是 0，所以会失败。

此外，它会对性能产生不良影响。素数测试的想法是检查所有数字，但不包括该数字。所以一个快速的解决方法是:

def p_number(a, b):
    pnumber = [x for x in range(a, b+1) if all(x % i for i in range(2, <b>x</b>))]
    print(pnumber)

我们可以通过使用 int(sqrt(x))+1 而不是 x 轻松地进一步提升它:

<b>from math import sqrt</b>

def p_number(a, b):
    pnumber = [x for x in range(a, b+1) if all(x % i for i in range(2, <b>int(sqrt(</b>x<b>))+1</b>))]
    print(pnumber)

我们可以进一步提升它，例如只评估奇数(并将结果加 2)。但是使用 sqrt 通常会带来显着的加速。