在 Python 中用模求素数

Question

我一直在为这段代码大费周章 -- returns 列表中的所有素数：

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 组件时，它 returns 从 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() 和 lambdas，所以我认为我可以弄明白，但我被难住了！我只是希望答案不会太明显以至于我觉得自己像个白痴...

Answer 1

我认为答案很简单。将您的素数集从 range(2,20) 增加到 range(2,30) 并再次尝试您的思想实验。这将使我更加明显。

过滤器函数将为

范围 (2,20) 的范围 return 取值

filter(lambda x: x == i or x % i, primes)

return正确。

除了将素数从 range(2,20) 增加到 range(2,30) 之外，使用您的内部过滤条件，您将开始看到您正在寻找的差异。

#!/usr/bin/python

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

print primes

这导致：

[2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29]

和

#!/usr/bin/python

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

print primes

结果

[2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29]

Answer 2

您发布的第一个代码块是我解释这一点的最简单示例：

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

使用 Sieve of Eratosthenes 方法时，需要注意的重要一点是，您只需删除作为数字乘积的数字直到 max[=38= 的平方根].上面 range(2,8) 的使用实现了这一点（它从 2 到 7，这比必要的更远）。 19的平方根（检查的外部范围内的最大数）在4到5之间。所以该范围内应该检查的最大数是4（我们只需要检查整数）。

利用这些知识，您可以改进代码如下（这会找到 <= 19 的素数）：

import math max = 19 #Set it here max += 1 primes = range(2, max) for i in range(2, int( math.ceil(math.sqrt(max)) )): primes = filter(lambda x: x == i or x % i, primes) print primes

请注意，我没有使用 floor 然后加一，因为 range 是独占的，我使用 ceil.

运行在这里：http://repl.it/8N8

编辑：我也意识到这（以及问题中提供的代码）并不是筛选方法的完整实现，因为根据算法，我们应该只标记素数，意思是内部使用range没有达到应有的效率。

查看正在进行的算法的图形说明：

Answer 3

它看起来像是埃拉托色尼筛法的紧凑（但有些晦涩）实现[编辑：正如评论中指出的那样，这实际上是一个 "unfaithful sieve"，因为试验划分导致 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 谓词过滤器的用途 --

包括我：x == 1
排除 i 的倍数：x % i -- 这是 x % i != 0 的简写形式。换句话说，x 不能被 i 整除，或者 x 不是 i 的倍数。

8 的上限似乎有些随意——至少，我们只需要搜索到 sqrt(n)，因为 sqrt(n) * sqrt(n) = n 意味着 sqrt(n) 是搜索的上限space.

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]

Answer 4

我写了一个简单的列表理解来生成素数。当然核心思想是在stack overflow里抄来的。老实说，我花了一些时间才理解它，因为我是 python 的初学者。我已经使用了这个列表理解单独调用 lambda 函数。所以首先我将讨论 lambda 函数。

lambda 函数： is_prime = lambda x: all(x % y != 0 for y in range(2,int(math.sqrt(x)) + 1))

现在使用上述 lambda 的列表理解。

primes = [x for x in range(30) if is_prime(x) == True]

Answer 5

此代码段将打印从 1 到 15 的质数：

lst = filter(lambda x: len(list(filter(lambda n: x % n != 0, range(2, x)))) == x - 2, range(15))
print (list(lst))

Answer 6

试试这个：

ip_list = [100, 200, 300, 17, 19, 23, 21]

is_prime = list(filter(lambda i: all(i%j!=0 for j in range(2, i//2)), ip_list))

print(is_prime)

Answer 7

这是获取 2 - 100 之间素数的代码

<code>Code :

l=list(filter(lambda x: not list(filter(lambda y : x%y==0, range(2,x))),range(2,100)))

在 Python 中用模求素数

Finding Primes with Modulo in Python

python

lambda

primes

modulus

sieve-of-eratosthenes