• 本文出自<svtter.github.io>

写在之前

maker关于线性筛素数的论文。

做到欧拉线性筛法再做补充。(当时还写了个这？)

关于线性筛素数

• 之前一直没有正视线性筛素数的问题。今天特意来写一个伪证明。如果当前的i不是素数，那么必然被之前的某个素数筛掉了。i × prime[j]。

  一个合数必然可以写成几个素数的乘积，再或者就是p×i这种形式。如果能被i×p1筛掉之后则不需要i×p2继续筛了，i×p2可以写成p1×(i×p2)

例如12可以被6×2筛掉，之前4×3这种筛除就可以去掉。

• 这种方法会不会存在没有筛掉的合数？

不可能：i会一直到n，也就是整个范围都会包含在内。

代码：

memset(Prime, , sizeof(Prime));
memset(IsPrime, 1, sizeof(IsPrime));
for(i = 2 ; i <= n; i++)
{
    if(IsPrime[i])
        Prime[num++] = i;
    for(j = ; j < num && i * Prime[j] <= n; j++)
    {
        IsPrime[i * Prime[j]] = ;
        if(i % Prime[j] == ) break;
    }
}

之前的错误在于筛素数的时候没有筛去2的倍数，所以出现后面的值错误。