怎么在自己做的网站上发视频/百度知道首页官网

线性素数筛也算是一种基本的算法吧，和背包一样，必须要做到深入理解其原理，并且能快速打出代码来。

两个大前提：

1. 自然数中，1既不是素数也不是合数。（小学知识）

2. 一个合数一定能分解成一个素数和另一个数相乘。（这个我不能证明，但是科学应该不会有错）

 

先从普通的思路谈起。

如果问你一个数是不是素数，那你一定是for循环一下，看看有没有数能够整除它。

现在，如果我们已经知道一个数是素数了，那么这个数的k倍（k>=2）,一定是合数。（这个无序任何证明）

所以一个很简单的想法就是每找到一个素数，我们就把它的k倍（k>=2）都标记为合数。所以我们需要开一个数组记录有哪些素数。

这里我们用prime[]数组来记录素数。用bool类型 isprime[]来记录一个数到底是不是素数。

按这个思路，我们可以先写一下初步的代码。

int prime[maxn],total;
bool isprime[maxn];
void first(int size){memset(isprime,1,sizeof(isprime));//注意这里isprime是布尔类型，一个字节，所以我可以赋值为1，如果是int类型，则不能赋值为1。isprime[1]=false;//1不是素数.for(int i=2;i<size;i++){if(isprime[i]){prime[++total]=i;//记录素数}for(int j=1;j<=total&&prime[j]*i<size;j++) //这里的i表示素数的多少倍{//也就是说每经历一个i，就要遍历当前已经找到的素数。isprime[i*prime[j]]=0;}}
}

但是你会发现复杂度不是o(n)。所以这里还需要一些优化。

我们来看一个很简单的例子：

当i=9时，当前已有的素数有2,3,5,7。

此时我将进入二重循环，一次将 2*9=18,3*9=27,5*9=45,7*9=63 标记为合数。

但是有个问题，5*9 等价于3*15,也就是说当i=15时，也会标记一次。这明显重复了。同理，7*9等价于3*21，当i=21时，也会重复标记一次。

多观察几组数据后，你会发现，其实只要找到i%prime[j]==0时，我们就可以跳出循环了，因为后面的素数的倍数，我们可以留到后面进行标记。那么这样的猜想到底对不对？下面看一个结论和证明。

假设 a,d为合数，b,c为素数  其中b>c.

a= b*c*d

令e=c*d(显然e也是合数)

令f=d*b(也是合数)

a=f*c  (f是合数，c是素数)。对比第一个等式,a=b*c*d  。我们发现a可以有这两种不同的表示方法，不同的是我们可以用一个较小的素数*一个较大合数  来代替   一个较大素数*一个较小合数（a=b*(c*d)）。

所以有下面的结论：

一个比合数大的素数和该合数的乘积可以用一个更大的合数和比其小的素数相乘得到。

 那么如何优雅的在代码里运用这个结论呢？

答案就是只要找到一个i%prime[j]==0 我们就跳出循环，因为后面总有更大的合数和一个小的素数相乘，满足我们需要标记的数。

最终代码：
 

void getPrime(int size)
{memset(isprime,1,sizeof(isprime));isprime[1]=false;for(int i=2;i<size;i++){if(isprime[i]){prime[++total] = i;}for(int j=1;j<=total&&i*prime[j]<=size;j++){isprime[i*prime[j]]=false;if(i%prime[j]==0){break;}}}
}

记在脑子里的才是自己的，模板都是虚假的。