为什么埃拉托斯特尼筛的第二圈是从当前素数的平方开始的？

Question

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;
            }
        }
    }

}

我的问题是为什么第二个循环从 i 的平方开始。当前素数(i)的平方之前的倍数是如何被标记的？实际上我们怎么这么确定？

Answer 1

如果我们已经标记了与

3*5

对应的条目，则标记与

5*3

对应的条目是没有意义的。

所以我们从

5*5

开始——就像我们之前从

3*3

开始一样，并且确实在循环

3*5 = 3*3+3+3

的过程中标记了

i=3

条目。

概括这个论点可以给你问题的答案。

Answer 2

以

i

为当前素数，其到

i*i

的倍数可写为：

i*(i-1)
i*(i-2)
 ⋮
i*(2)

它们包括小于

i

的除数，并且这些除数已经在之前的循环中考虑过。例如，

i*(2)

已被划掉（标记为 False）作为数字 2 的倍数，

i*(7)

已被划掉（标记为 False）作为数字 7 的倍数，

i*(i-1)

已被划掉（标记为 False）作为数字

i-1

的倍数。所以不需要再次划掉这些数字，只需从

i*i

开始即可。