对线性筛的理解

线性筛

思想:每个数有且仅筛一次
解决:每个数只被其最大因子(非本身)筛去

设合数x最小素因子为p,x=pq,易知p<=q

我们让x只被q筛去,选择枚举q

枚举q时,找到所有满足的p,筛去数x,一个不漏

void sieve() {
	for(int i=2;i<=m;i++) { //枚举q 
	    if(v[i]==0) {
	    	ps[++cnt]=i; //统计p 
		}
		for(int j=1;j<=cnt;j++) { //枚举满足的p 
			if(i*ps[j]>m) break;
			v[i*ps[j]]=1;
			if(i%ps[j]==0) break; //条件判断 
		}
    }
} //统计2到m的质数 

上述代码意思是:设q最小素因子为u,q=uv

1.若p<=u(p是质数),则p是x=pq的最小素因子,满足条件,筛去x

2.若p>u,x=pq=puv=u*(pv),p不是x最小素因子,这个数会被pv(大于q)筛去,重复了,可以跳出不再筛x

至此,这个算法的正确性和充分性都被证明了.

(原创)

对线性筛的理解对线性筛的理解 cqbzlydd 发布了1 篇原创文章 · 获赞 0 · 访问量 41 私信 关注
上一篇:小凯的疑惑


下一篇:LeetCode 451.根据字符出现频率排序