赞
踩
欧拉筛法的一些笔记
看了一些大牛的心得,总结了一下自己的心得
代码所示:
#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; } } }
关键一步:因为这个表是按照递增顺序的,所以当i%prime[j]==0的时候,说明i的最小质因子已经出现了。设i=nprime[j];
又因为 是递增的 prime[j+1]>prime[i]
所以 iprime[j+1]=n*prime[j]*prime[j+1]
不是按照最小的质因子去筛,这样将会重复筛去,不能达到o(n)的时效。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。