在 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)))
我一直在为这段代码大费周章 -- 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)))