浅谈欧拉筛

\(updata : 2021.12.15\)

理解合数的唯一分解定理对欧拉筛的原理有帮助.

先贴代码

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

\(① :\) if(! vis[i] ) Q[++l] = i

将是素数的加入队列之中，注意为什么没有被访问到的数就是素数呢? 利用合数唯一分解定理就可以证明 , 它分解的素数永远比它小 , 总会存在一种组合 , 使它被一组比它小的素数乘积遍历到(可能为素数 \(\times\) 合数 , 但这个合数何尝不是一组更小的素数的乘积呢)

\(② :\) vis[Q[j] * i] = 1

前面说过了 \(i\) 是合数也没有关系 , 合数就是一组质数的乘积 , 这是符合唯一分解定理的 , 根据唯一分解定理 , 我们能保证每个合数在 \(i\) 循环到它之前都会被遍历到.

\(③ :\) if(i % Q[j] == 0) break;

算法剪枝之处 , 要保证每个合数被最小的素数( Q[j] )筛出 , 一旦 \(i\) 是 Q[j] 的倍数(不管 \(i\) 是质数还是合数) ,
\(i \times\) 质数 (这里的质数大于Q[j]) 都不如 Q[j] \(\times\) 更大的质数筛去，因为后者能保证唯一分解 .至于在遇到Q[j] , 之前被筛去的数 \(i \times\) Q[k] , (\(k < j\)) , 这些数也是被唯一筛去的 , 这是的 \(i\) 被 Q[k] 当作前文提及的 “更大的质数” 来看待.

算法理解

浅谈欧拉筛

相关

标签