埃拉托斯特尼筛法

埃拉托斯特尼筛法

The Greek mathematician Eratosthenes proposed a simple algorithm for identifying prime numbers. To obtain all prime numbers less than or equal to a natural number, one must eliminate all multiples of prime numbers not greater than, and the remaining numbers will be prime.

希腊数学家埃拉托斯特尼所提出一种简单检定素数的算法。要得到自然数 以内的全部素数，必须把不大于 的所有素数的倍数剔除，剩下的就是素数。

Next, I will manually demonstrate how to obtain all the prime numbers within a certain range.

下面我将手动演示如何获得某个区间的所有素数。

Write integers of about.

写出大约 的整数。

Leaving unchanged, remove all the numbers in the number table that are multiples of to get:

保持 不变，删掉所有 的倍数，得到：

The first number after is. Keep and unchanged, and remove all the numbers in the number table that are multiples of to get:

之后的第一个数字是 ，保持 和 不变，删掉所有 的倍数，得到：

The first unaffected number after is. Leaving,, and unchanged, and discarding all multiples of in the number table, we get:

之后的第一个不受影响的数字是 ，保持,, 不变，删掉所有 的倍数，得到：

The first number not affected is. The next step is to leave,,, unchanged, and eliminate all the numbers in the table that are multiples of.

之后的第一个不受影响的数字是 ，保持,,, 不变，删掉所有 的倍数。

…………

The last remaining numbers are prime numbers.

最后剩下的数字是素数。

This is the Sieve of Eratosthenes.

这是埃拉托斯特尼筛法。