在 Python 中用模求素数

Finding Primes with Modulo in Python

我一直在为这段代码大费周章 -- 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,所以我认为我可以弄明白,但我被难住了!我只是希望答案不会太明显以至于我觉得自己像个白痴...

我认为答案很简单。将您的素数集从 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]

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

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没有达到应有的效率。

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

它看起来像是埃拉托色尼筛法的紧凑(但有些晦涩)实现[编辑:正如评论中指出的那样,这实际上是一个 "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]

我写了一个简单的列表理解来生成素数。当然核心思想是在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]

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

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

试试这个:

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)

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

<code>Code :

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