埃拉托斯特尼筛法第二层循环为何从当前素数的平方开始？

现有实现代码 #

vector<bool>vc(100006,1);
void seive(int n)
{
    vc[0]=vc[1]=0;
    int i,j;
    for(i=2;i*i<=n;i++)
    {
        if(vc[i]==1)
        {
            for(j=i*i;j<=n;j=j+i)
            {
                vc[j]=0;
            }
        }
    }
}

问题解答 #

1. 为何第二层循环要从i的平方位置开始遍历？ #

核心目的是避免重复标记已被处理过的非素数，降低无效计算量，提升筛法运行效率。如果将内层循环起始值改为2*i，最终筛出的素数结果完全一致，但会重复标记大量已经被更小素数处理过的合数，执行步骤会多出很多。

2. 小于当前素数i平方的i的倍数是如何被标记为非素数的？ #

所有小于i²的i的倍数都可以表示为k*i，其中k < i：

• 若k本身是素数，那么k*i这个合数早在外层循环遍历到k的时候，就已经被k的内层循环标记为非素数
• 若k是合数，那么k必然存在至少一个小于k的素因子，k*i也会在更早的遍历步骤中被这个更小的素因子标记

举个实际例子说明：当i=5时，小于5²=25的i的倍数为10、15、20：

• 10=2*5，在i=2的遍历步骤中就已被标记
• 15=3*5，在i=3的遍历步骤中就已被标记
• 20=2*10，同样在i=2的遍历步骤中就已被标记

所以这部分数不需要等到遍历到i的时候再重复处理。

3. 该设计的理论依据是什么？ #

设计的核心理论依据是算术基本定理：任何大于1的合数都可以唯一分解为有限个素数的乘积，且该合数的最小素因子一定小于等于它的平方根。
对于当前遍历到的素数i来说，所有以i为最小素因子的合数，必然可以写成i*m的形式，其中m ≥ i——如果m < i，那么m的素因子都会小于i，对应合数的最小素因子就不会是i，早就被更小的素数处理完成。i*m的最小取值就是i*i，所以从i平方开始遍历，刚好只会处理未被标记过的、最小素因子为i的合数，没有冗余操作。

内容的提问来源于stack exchange，提问作者Roman