素数筛
顾名思义, 用来筛选素数.
这里介绍两种素数筛:
1. 埃氏筛 (埃拉托斯特尼筛法)
- void ass()
- {
- memset(u,true,sizeof(u));//u[i]=true 表示 i 是素数
- for(int i=2; i<=1100000; i++)
- {
- if(u[i])
- for(int j=2; j<=1100000; j++)
- {
- if(i*j>1100000) break;
- u[i*j]=false;// 素数 *j(j>=2) 一定是合数
- }
- }
- }
2. 欧拉筛
- void olas()//su[] 用来存素数的值
- {
- int i,j;
- num=1;//num 记录素数个数
- memset(u,true,sizeof(u));//u[i]=true 表示 i 是素数
- for(int i=2;i<=1000000;i++)
- {
- if(u[i]) su[num++]=i;
- for(int j=1;j<num;j++)
- {
- if(i*su[j]>1000000) break;// 超出判定的范围
- u[i*su[j]]=false;// 因为素数 *i(i>=2) 一定是合数.
- if(i%su[j]==0) break;// 这个是欧拉筛减少时间开销的关键
- }
- }
- }
来源: http://www.bubuko.com/infodetail-3163612.html