超出O（n）的Eratosthenes筛。 证明

在对先前有关Eratosthenes筛子的帖子的评论中，提到了Wikipedia的这种简短算法：

算法1：

1:  i := 2, 3, 4, ...,  n: 2:  lp[i] = 0: 3: lp[i] := i 4: pr[] += {i} 5:  p  pr  p ≤ lp[i]  p*i ≤ n: 6: lp[p*i] := p : lp -        n pr -     n. 

该算法很简单，但并不是所有人都看得出来。 主要问题是维基百科上没有证据，并且到源的链接 （ pdf ）包含与上述算法完全不同的算法。

我希望，在本文中，我将尝试证明该算法不仅有效，而且对于线性复杂度也可以实现。

定义

$$$\数学{P}$ -很多素数
$$$lp（x）$ -最小最小素数： $$$lp（x）=最小值\ {p \ in \ mathcal {P} \ \ vert \ p \ vert x \}$
$$$rd（x）$ -其他因素： $$$rd（x）= x / lp（x）$

请注意，以上所有定义都是针对 $$$x \ ge 2$ 。

上面介绍的功能的一些明显属性，将在以后使用：
$$$lp（a \乘以b）= min（lp（a），lp（b））$
$$$rd（x）<x$
$$$p \ in \ mathcal {P} => lp（p）= p$

证明

引理1 ： $$$lp（x）\ le lp（rd（x）），\ forall x \ notin \ mathcal {P}，x> 1$
证明 ：因为 任何除数 $$$rd（x）$ 也是一个分隔线 $$$x$ 和 $$$lp（x）$ 不胜于任何除数 $$$x$ 然后 $$$lp（x）$ 不超过任何除数 $$$rd（x）$ 包括最小的。 该语句的唯一问题是 $$$rd（x）$ 没有简单的除数，但这只有在 $$$x \ in \ mathcal {P}$ ，在引理条件下被排除。
$$$\平方$

让 $$$E = \ {（lp（x），rd（x））\ vert \ forall x \ notin \ mathcal {P}，2 \ le x \ le n \}$

因为 $$$lp（x）\乘rd（x）= x$ （根据定义 $$$rd（）$ ），如果我们得到了很多 $$$E$ 然后我们可以计算 $$$lp（）$ 对于所有不超过n的复合数字。 例如，这可以通过以下算法完成：

算法2：

 1:   (l,r)  E: 2: lp[l*r] := l; 

注意 $$$\ vert E \ vert \ le n$ 因此，上面的算法2适用于线性复杂度。

此外，我将证明Wikipedia的算法1实际上只是对该集合的所有元素进行迭代，因为可以用不同的方式对其进行参数化。

让 $$$E'= \ {（p，r）\ vert p \ in \ mathcal {P}，2 \ le r <n，p \ le lp（r），p \ times r \ le n \}$

引理2 ： $$$E = E'$
证明 ：

让 $$$（a，b）\在E$ => $$$\存在x \ notin \数学{P}，\ 2 \ le x \ le n \ mid a = lp（x），b = rd（x）$ 。

根据定义 $$$lp（），rd（）$ ： $$$a \ in \ mathcal {P}$ ， $$$a \乘以b = x$ 。 通过引理1， $$$a \ le lp（b）$ 。
因为 $$$rd（x）<x$ 然后 $$$b <n$ 。
由于 $$$x \ notin \ mathcal {P}$ ， $$$b \ ge 2$ 。
另外，根据定义 $$$E$ ， $$$x \ le n$ 因此 $$$a \倍b \ le n$ 。
全部4个条件 $$$E'$ 履行手段 $$$（a，b）\在E'$ => $$$E \子集E'$ 。

让 $$$（a，b）\在E'$ 。 让 $$$x = a \乘以b$ 。
根据定义 $$$E'$ ， $$$a \ in \ mathcal {P}$ 。 均值 $$$一$ -简单的划分 $$$x$ 。
$$$lp（x）= lp（a \乘以b）= min（lp（a），lp（b））= min（a，lp（b））$
因为 $$$a \ le lp（b）$ 然后 $$$lp（x）= a。$ 均值 $$$b = rd（x）$
根据定义， $$$x = a \乘以b \ le n$ 也很明显 $$$x = a \乘以b \ ge 2$
的所有条件 $$$E$ 完成=> $$$E'\子集E.$

因此 $$$E = E'。$
$$$\平方$

现在仍然有必要找出正确的 $$和 $$$p$ 从集合的定义 $$$E'$ 并应用算法2。这正是算法1所做的（仅使用i变量而不是r）。 但是有问题！ 排序集合中的所有元素 $$$E'$ 计算 $$$lp，$ 我们需要知道 $$$lp，$ 因为定义中有条件 $$$p \ le lp（r）$ 。

幸运的是，这个问题可以解决正确的排序顺序。 有必要理清 $$在外循环中，以及 $$$p$ -在里面。 然后 $$$lp（r）$ 将已经计算出来。 以下定理证明了这一事实。

定理1：
算法1支持以下不变量：在对i = k的外循环进行迭代之后，直到pr（包括k）的所有素数都将在pr中突出显示。 也将算在内 $$$lp（）$ 对于所有 $$$x \ notin \ mathcal {P} \ mid x \ le n，\ rd（x）\ le k$ 在lp数组中。

证明 ：
我们通过归纳证明。 当k = 2时，手动检查不变量。 唯一的质数2将添加到pr列表中，因为lp []数组最初使用零填充。 另外，唯一的化合物编号 $$$rd（x）\ le 2$ -这是4。很容易验证内部循环将只执行一次（对于n> 3）并正确执行lp [4]：= 2。

现在假设不变量对于迭代i = k-1成立。 让我们证明它对于迭代i = k也将是有效的。

为此，只需检查数字i（如果为质数）将被添加到列表pr中， $$$lp（）$ 将计算所有复合数字 $$$x \ le n，$ 包括 $$$rd（x）= i。$ 这些来自k不变式的数字尚未被k-1不变式覆盖。

如果i很简单，则lp [i]将为0，因为对数组lp的唯一写操作（理论上可以计算lp [i]（在第6行））总是写到复合索引，因为p * i（对于i> 1）-总是复合的。 因此，数字i将被添加到素数列表中。 同样，在第3行中，将计算lp [i]。

如果i是合成的，那么在迭代开始时lp [i]就已经由i = k-1的不变量计算出来了，因为 $$$rd（i）<i$ 或 $$$rd（i）\ le i-1，$ 因此，我在上一次迭代中处于不变条件下。 因此，合成数字i不会添加到素数列表中。

此外，具有正确的lp [i]和所有素数，直到i（含i）为止，第5-6行中的循环将迭代所有元素 $$$（p，i）\ E'$ 其中第二部分是我：

• $$$p \在P，$ 因为它来自列表pr
• $$$p \ le lp（i），$ 根据条件停止循环
• $$$p \次i \ le n，$ 根据条件停止循环
• $$$i <n，$ 从... $$$p \次i \ le n，\ p> 1$

pr列表中所有必要的素数是，因为 最多不超过 $$$lp（i）\ le i$ 。 因此，将为所有复合数字计算lp []值 $$$x$ 为此 $$$rd（x）=我$ 。 这些恰好是从k-1不变式到k不变式转换过程中丢失的所有数字。

因此，对于任何i = 2..n，不变量成立。

$$$\平方$

通过定理1中i = n的不变量，可以得出直到n的所有素数，所有lp []都将由算法1计算。

此外，由于在第5-6行中对集合的各个元素进行了排序 $$$E$ ，则整个内部循环将不再执行 $$$\ vert E \ vert <n$ 操作。 循环中的检查操作将顺利运行 $$$\ vert E \ vert + n-1 <2n$ 次（ $$$\版本E \版本$ 次将返回true，n-1次，对于每个i，将返回false）。 所有剩余的操作都在i中从2到n的一个循环中嵌套。
因此，算法1的复杂度为O（n）。