python - 在 Python 中使用模查找素数

Question

这段代码让我费尽了心思——它返回列表中的所有素数:

primes = range(2, 20) 
for i in range(2, 8): 
     primes = filter(lambda x: x == i or x % i, primes)

print primes

它有效...但我不明白“x == i or x % i”在整个过程中扮演的角色。

我也不明白为什么第二个范围只有2到7。

我什至创建了埃拉托色尼筛法的 Python 实现，希望它能给我一些见解，但它没有。

当我删除 x % i 组件时，我希望这段代码能为我提供两组共有的数字，但它没有:

nums = [2, 20] 
for i in range(2, 8): 
     nums = filter(lambda x: x == i, nums)

print nums

这是为什么？

同样，当我删除 x == i 组件时，它会返回从 11 到 19 的素数。

nums = range(2, 20) 

for i in range(2, 8): 
     nums = filter(lambda x: x % i, nums)

print nums

同样，我不明白为什么它会忽略所有小于 11 的素数。

接下来，我尝试了这个:

nums = [13] 

for i in range(2, 8): 
     nums = filter(lambda x: x % i, nums)

print nums

同样，这对我来说毫无意义。 lambda 在 nums 中迭代 x 对吗？ i 在 2 到 7 的范围内迭代。那么，我们不是将 13 % i... 用于 2 到 7 吗？这如何导致“13”？

使用与上面相同的逻辑，我对“13”做了同样的事情，但在 lambda 中使用了 x == i。

for i in range(2, 8): 
     nums = filter(lambda x: x == i, nums)

print nums

正如我所料，它返回了一个空列表——这在我看来是有道理的，因为 13 从未出现在 2 到 7 的范围内。

对于任何试图提供帮助的人来说，这是我在使用 filter() 和 lambdas 时的心态:

a = range (1, 11)
b = range (9, 20) 

for i in filter(lambda x: x in a, b):
    print i,

当然，这给了我们“9 10”。我知道循环的结构不同，但希望它能帮助您了解我的困惑所在。

我已经广泛使用了 filter() 和 lambda，所以我认为我可以弄明白，但我被难住了!我只希望答案不会太明显以至于我觉得自己像个白痴...

Answer 1

它看起来像是 Eratosthenes 筛法的紧凑(但有些晦涩)实现 [编辑:正如评论中指出的那样，这实际上是一个“不忠实的筛子”，因为试验部门导致 worse time complexity比实际的埃拉托色尼筛法]。

第一行只是连续整数的任意搜索范围，用于过滤素数:

primes = range(2, 20)

接下来，following the sieve algorithm ，我们用范围 (2, n) 中的整数 i 进行迭代，其中 n 天真地是搜索范围中的最大数字(尽管在这种情况下，7 是选择的上限——更多内容见下文)。

for i in range(2, 8): 
    primes = filter(lambda x: x == i or x % i, primes)

该算法声明我们包含 i 并排除i 的倍数。这就是 lambda 谓词过滤的目的——

• 包含 i: x == 1
• 排除 i 的倍数:x % i -- 这是 x % i != 0 的简写。换句话说，x 不能被 i 整除，或者 x 不是 i 的倍数。

8 的上限似乎有些随意——最低限度，我们只需要搜索到 sqrt(n)，因为 sqrt(n) * sqrt(n) = n 表示 sqrt(n) 是搜索空间的上限。

19 的平方根约为 4.4，在此示例中，您会看到素数列表在 i = 3 后没有变化。

In [18]: primes = range(2, 20)

In [19]: for i in range(2, 8):
   ....:     primes = filter(lambda x: x == i or x % i, primes)
   ....:     print i, primes
   ....:
2 [2, 3, 5, 7, 9, 11, 13, 15, 17, 19]
3 [2, 3, 5, 7, 11, 13, 17, 19]
4 [2, 3, 5, 7, 11, 13, 17, 19]
5 [2, 3, 5, 7, 11, 13, 17, 19]
6 [2, 3, 5, 7, 11, 13, 17, 19]
7 [2, 3, 5, 7, 11, 13, 17, 19]