NO1
快速线性筛求素数问题 (欧拉筛法)
特点: 没有冗余, 不会重复筛除一个数. 其时间复杂度几乎为 O(n).
原理: 对于任意合数, 必定可以有最小质因子乘以最大因子的分解方式. 因此, 对于每个合数, 只要用最大因子筛一遍, 枚举时只要枚举最小质因子即可.
- #include<iostream>
- #define MAXN 1000010
- using namespace std;
- long prime[MAXN],number_prime; //prime 为素数的集合, number_prime 为素数的个数
- bool vis[MAXN]; //vis 用于记录那些数不是素数
- inline void pd_prime(int number) //number 是所求素数集合的上限
- {
- for(int i=2;i<=number;i++)
- {
- if(!vis[i]) prime[number_prime++]=i; // 如果不在 非素数集合内 判定为素数 -- 同时 number+1 (此时是 number 先赋值再 + 1, 故 prime 序列从 0 开始)
- for(int j=0;j<number_prime && i*prime[j]<=number;j++) //j 要小于现在求出来的素数个数, 并且下一步筛出的那个数 (i * 某已知素数要小于要求的上限)
- {
- vis[i*prime[j]]=true; // 能拆成 i * 质数 为合数 筛出
- if(!(i%prime[j])) break; // 见注解 1 i%prime[j]==0
- }
- }
- }
- int main()
- {
- int n;
- cin>>n;
- pd_prime(n);
- for(int i=0;i<number_prime;i++) cout<<prime[i]<<endl;
- cout<<endl<<"total number:"<<number_prime;
- return 0;
- }
注解 1: 只筛最小质因子
eg: 12=2*2*3
当 i=4 时, 将 4*2 筛除 --- 停止
......
当 i=6 时, 将 6*2 筛除 ---6*3 筛除 --- 停止
12 的最小质因子为 2, 只在 i=2 时筛了一遍
若 i=p1*p2*......*pn 设 p2*......*pn 为 q 则只筛除 x=i*p1 即 x= p1 * p1 *q. 其余的合数 如: x2=p2*p1*q = (p2 * p2* ...... *pn) * p1; 在 i=(p2 * p2* ...... *pn) 时自然会筛除.
来源: http://www.bubuko.com/infodetail-3345141.html