• 欢迎光临~

线性筛(欧拉筛)详解

开发技术 开发技术 2022-07-29 次浏览

看到埃氏筛的缺点,同学们可能会想,有没有筛法能够将一个数只筛一遍呢?答案是肯定的。

线性筛思想:这个合数只会被它的最大非自身因数(对应最小质因数)筛。 这样能保证每个合数只会被筛一次。
时间复杂度:(O(n)),

Code:

bool a[50000];
a[1]=1;//注意1不是质数;
int p[50000],t;
for(int i=2;i<=n;i++)
{
	if( a[i] == 0 )
		p[++t]=i;//是质数就记录;
	for(int j=1;j<=t && i*p[j]<=n;j++)
	{
		a[ i*p[j] ]=1;//标记合数;
		if( i%p[j] == 0 )
			break;
		//保证同一个合数不会被多个质数标记。
	}
}

最小质因数 × 最大因数(非自己) = 这个合数

(p) 数组中的质数是递增的,当i能整除 (p[ j ]) ,那么 (itimes p[j+1]) 这个合数肯定会被 (p[ j ]) 乘某个数筛掉。因此直接 (break),将 (itimes p[j+1])以及之后的数筛掉。

这个方法可以保证每个数都被筛掉,但又只被筛一次。

程序运行:2 加入 (p) 数组,枚举质数(只有2),筛去质数与 2 的乘积(筛去 4)。3 加入 (p) 数组(现在有2、3),枚举质数,筛去 3 与质数的乘积(筛去6、9)。4 不是质数,不加入 (p) 数组,枚举质数,筛去8;此时 (4 mod 2=0) ,触发了 (break)

如果你还不理解,让我们来看表格。

i 质数 筛去的合数
2 2 4
3 2、3 6、9
4 2、3 8
5 2、3、5 10、15、25
其余以此类推。
程序员灯塔
转载请注明原文链接:线性筛(欧拉筛)详解
喜欢 (0)