只需要一条 Python 指令,即可找出指定范围内(如100以内)的全部质数。
print([2]+(lambda n,s=set():[i for i in range(3,n+1,2) if ([j for j in range(i*3,n+1,i*2) if s.add(j)] or i not in s)])(100))
# 运行结果
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
Wow!如何做到的?首先明确以下几点:
- 最小的质数 2,也是质数中唯一的偶数
- 3 是质数中最小的奇数
- 每一个合数都可以表示为若干个质数之积
那么寻找 $U={(2,n]\cap \mathbb{N}}$ 中的质数思路如下:
- 质数一定在奇数中,去除 $U$ 中的偶数,得到 $U_o$
- 记 3 为 $p$
- 去除 $U_o$ 中 $p$ 或者 $p^\ast$ 的倍数,得到 $U_o^\ast$
- 记 $p+2$ 为 $p^\ast$
- 如果 $p^\ast\in U_o^\ast$,那么 $p^\ast$ 就是质数
- 如果 $p^\ast< n$,跳至步骤 3
上述程序中:
i for i in range(3,n+1,2)
给出了 $U_o$j for j in range(i*3,n+1,i*2)
表示i
的奇数倍if s.add(j)
将i
的奇数倍添加至集合s
中,即s
是合数集- 由于
s.add(j)
为假,因此[j for j in range(i*3,n+1,i*2) if s.add(j)]
是一个空列表 []
亦为逻辑假,因此if ([] or i not in s)
的逻辑值只与i not in s
有关[i for i in range(3,n+1,2) if i not in s]
即为 $U_o$ 与合数集s
的差集- 将
[2]+
加入列表,从而得到(100)
以内的质数集
巧妙之处在于:
- 不直接从质数定义着手,而采用排除法剪枝;
- 借用列表推导式进行循环操作;
- 以逻辑判断的名义,进行
s.add(j)
操作。