快速线性筛

快速线性筛可以使我们能够在线性时间内筛出特定区间内的素数。
代码的基本思路是，开两个数组num[x]和prime[x]，其中前者记录(x)是否为素数，后者记录第(x)个素数。遍历给定的区间，对于当前考虑的数(x)，先判断num[x]上的记录，如果是素数则加入prime数组中。然后在把这个数分别乘以prime数组上的素数，将这些积也标记为合数，如果碰到x%prime[j]==0的情况，则跳出循环，继续考虑(x+1)。
这样做可以保证筛每个数都能做到不重不漏，而此算法有别于普通线性筛的关键在于x%prime[j]==0这条语句。
现在大概阐释下算法的正确性。首先，正确性有赖于 算术基本定理 ，关于此定理的具体内容在此不再赘述。此处引用网上的一个证明。

对于一个数(c=ab)((b)为(c)的最小质因数），当通过该算法的循环循环至(cb)时，易得此时(c mod b=0),如果此时继续循环至(b)后面的一个素数(d)，则有：(cd=abd=ad imes b)，因为(d>b)，所以(a d>c)。当循环从(c)继续查找到(ad)时我们发现当(ad)再次与素数(b)相乘时，就又对(cd)进行了一次操作，出现了冗余，所以在if(n%prime[j]==0)成立时要将该层循环跳出。

核心代码如下：

for(int i=2;i<=n;++i)
{
	if(!num[i]) prime[++cnt]=i;
	for(int j=1;j<=cnt && i*prime[j]<=n;++j)
	{
		num[i*prime[j]]=1;
		if(i%prime[j]==0) break;
	}
}