当前位置:   article > 正文

寒假训练 ACM笔记心得--欧拉筛法

欧拉筛法

欧拉筛法的一些笔记

看了一些大牛的心得,总结了一下自己的心得

代码所示:

#include<iostream>
using namespace std;
#define maxn ;
int main()
{
int sum=1;
int prime[maxn];
int vis[maxn];
 for(int i=2;i<maxn;i++)
{
if(!vis[i])
prime(sum++)=i;//找素数,把当前最小素数从筛子中,打入表里
    	   for(j=1;j<sum&&i*prime[j]<maxn;j++)//从表中选取这些数,依次翻倍
    	{
		vis[i*prime[j]]=1;//将这个数的i倍从筛子中删去
		if(i%prime[j]==0)//**关键的一步 放在后面讲**
		break;
		}

}

}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

关键一步:因为这个表是按照递增顺序的,所以当i%prime[j]==0的时候,说明i的最小质因子已经出现了。设i=nprime[j];
又因为 是递增的 prime[j+1]>prime[i]
所以 i
prime[j+1]=n*prime[j]*prime[j+1]
不是按照最小的质因子去筛,这样将会重复筛去,不能达到o(n)的时效。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/知新_RL/article/detail/947540
推荐阅读
相关标签
  

闽ICP备14008679号