只需要一条 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}}$ 中的质数思路如下:

  1. 质数一定在奇数中,去除 $U$ 中的偶数,得到 $U_o$
  2. 记 3 为 $p$
  3. 去除 $U_o$ 中 $p$ 或者 $p^\ast$ 的倍数,得到 $U_o^\ast$
  4. 记 $p+2$ 为 $p^\ast$
  5. 如果 $p^\ast\in U_o^\ast$,那么 $p^\ast$ 就是质数
  6. 如果 $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) 以内的质数集

巧妙之处在于:

  1. 不直接从质数定义着手,而采用排除法剪枝;
  2. 借用列表推导式进行循环操作;
  3. 以逻辑判断的名义,进行 s.add(j) 操作。
如果您喜欢这篇文章,欢迎转载、演绎或用于商业目的,但请务必保留作者署名以及本文链接!
Copyright © Pandaman