关于线性筛的一些思考

	memset(is_prime,true,sizeof(is_prime));
	is_prime[0]=is_prime[1]=false;
	for(int i=2;i<=L;i++)
	{
		if(is_prime[i])prime[++cnt]=i;
		for(int j=1;j<=cnt;j++)
		{
			int x=i*prime[j];
			if(x>L)break;
			is_prime[x]=false;
			if(i%prime[j]==0)break; 
		}
	}

这是代码
思考几个问题
1.它是怎样达到O(n)的？
2.为什么i%prime[j]时应该break

首先，达到O(n)的原理————————每一个数只会被唯一的一个数给筛掉
如12会被6筛掉 18会被9筛掉
具体来说，x会被x/d筛掉，d是x的最小的质因数

举例来说
12-->6-->3-->1 322=12
18-->9-->3-->1 332=12
180-->90-->-->45-->15-->5-->1 53322=180
显然这种划分的方式是唯一的。
为了实现这个功能
便有了

if(i%prime[j]==0)break; 

这样一句话
比如4的时候，4%2==0，不会再去用4去筛掉12
而是等到6再去用6筛掉12
这是因为发现了4的最小质因数为2，于是就不考虑用更大的质因数了
所以直接break即可

关于线性筛的一些思考

原文：https://www.cnblogs.com/Creed-qwq/p/13501520.html