Sieve of Eratosthenes · 埃拉托色尼筛法
Sieve of Eratosthenes
The Greek mathematician Eratosthenes found primes without dividing anything: write down the numbers, then cross out the multiples of each prime.
[True] * (n + 1) makes a list of n + 1 True values, one for each number from 0 to n. Mark 0 and 1 as not prime. Then, for each p still marked True, set every multiple of p from p * p onwards to False. The numbers still marked True at the end are the primes.
埃拉托色尼筛法
古希腊数学家埃拉托色尼不用做除法就能找出素数：先把数写下来，再划掉每个素数的倍数。
[True] * (n + 1) 生成一个含有 n + 1 个 True 的列表，对应从 0 到 n 的每个数。把 0 和 1 标记为不是素数。然后，对每个仍然标记为 True 的 p，把从 p * p 开始的每个 p 的倍数设为 False。最后仍然是 True 的数就是素数。
Write primes_up_to(n) that returns every prime number from 2 to · 到 n in order, using the sieve of Eratosthenes. primes_up_to(10) is [2, 3, 5, 7]. · 编写 primes_up_to(n)，用埃拉托色尼筛法按顺序返回 2 到 n 之间的所有素数。primes_up_to(10) 是 [2, 3, 5, 7]。
Click Run to see the output here. · 点击“运行”查看此处输出。