跳到主要内容

埃拉托色尼筛法

埃拉托色尼筛法

古希腊数学家埃拉托色尼不用做除法就能找出素数:先把数写下来,再划掉每个素数的倍数。

[True] * (n + 1) 生成一个含有 n + 1 个 True 的列表,对应从 0 到 n 的每个数。把 0 和 1 标记为不是素数。然后,对每个仍然标记为 True 的 p,把从 p * p 开始的每个 p 的倍数设为 False。最后仍然是 True 的数就是素数。

登录或创建账户

IGCSE, A-Level & AP