将优化的Eratosthenes筛网从Python移植到C ++

将优化的Eratosthenes筛网从Python移植到C ++

我会尽力解释。该

sieve

数组具有不同寻常的索引方案；它为每个

6*k + 1

等于1或5 mod
6的数字存储一个位。因此，一个数字将存储在position

2*k

并将

k*6 + 5

存储在position

2*k +1

。在

3*i+1|1

*** 作中，该逆：其形式的数字

2*n

并将它们转换成

6*n + 1

，并采取

2*n + 1

并将其转换成

6*n +5

（的

+1|1

东西转换

0

到

1

和

3

到

5

）。主循环遍历

k

具有该属性的所有数字，从

5

（when

i

为1）开始；

i

是对应的索引

sieve

为号

k

。第一个分片更新为

sieve

然后用形式

k*k/3+2*m*k

为

m

自然数的索引清除筛子中的所有位；这些索引的相应数字从处开始

k^2

并

6*k

在每一步处增加。第二切片更新开始于索引

k*(k-2*(i&1)+4)/3

（号码

k* (k+4)

为

k

全等到

1

MOD

6

和

k * (k+2)

其他），并通过数同样增加

6*k

在每个步骤。

这是另一种解释的尝试：让

candidates

所有数字的集合至少为5，并且等于

1

或

5

mod

6

。如果您将该集合中的两个元素相乘，则会在该集合中获得另一个元素。让

succ(k)

一些

k

在

candidates

在成为下一个元素（以数字顺序）

candidates

是大于

k

。在这种情况下，筛网的内部循环基本上是（使用的常规索引

sieve

）：

for k in candidates:  for (l = k; ; l += 6) sieve[k * l] = False  for (l = succ(k); ; l += 6) sieve[k * l] = False

由于存储在中的元素的限制，因此

sieve

与：

for k in candidates:  for l in candidates where l >= k:    sieve[k * l] = False

它将在某个点（无论是以前使用电流还是现在使用电流）从筛子中除去

k

in的所有倍数

candidates

（

k

本身除外）。

k``l``k