埃氏筛法
/*
|埃式筛法|
|快速筛选素数|
|15-7-26|
*/
#include <iostream>
#include <cstdio>
using namespace std;
const int SIZE = 1e7; int prime[SIZE]; // 第i个素数
bool is_prime[SIZE]; //true表示i是素数 int slove(int n)
{
int p = ;
for(int i = ; i <= n; i++)
is_prime[i] = true; //初始化
is_prime[] = is_prime[] = false; //0,1不是素数
for(int i = ; i <= n; i++)
{
if(is_prime[i]) //这里比较巧妙, 我只是意会
{
prime[p++] = i; //计算素数的个数,也记录下了素数
for(int j = * i; j <= n; j += i) // 除掉了i的倍数的数字
is_prime[j] = false;
}
}
return p;
} int main()
{
int n;
while(cin >> n)
{
int res = slove(n);
cout << res << endl;
for(int i = ; i < res; i++)
cout << prime[i] << endl;
}
}
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 2 | 3 | - | 5 | - | 7 | - | 9 | - | 11 | - |
| 2 | 3 | - | 5 | - | 7 | - | - | - | 11 | - |
结合这张表看看,慢慢一次次的都筛选完了..
其中最小的素数是2,将表中所有2的倍数都除去,剩下最小的数是3,不能被更小的数整除,所以是素数.再将表中3的倍数的数除去.以此类推.如果表中最小的数字是m,m就是素数.然后将表中所有m的倍数都除去...然后就可以了= =
话说要是求区间[x,y]内求素数个数的话,只要0~y的素数个数-0~x的素数个数就可以了,然后判断x是否为素数就可以了...
欧拉函数
#include<cstdio>
#include<cmath>
using namespace std;
#define m 5800000
#define m1 100000000
int n,len,a[m];
bool vis[m1];
int main()
{
scanf("%d",&n);
for(int i = ;i <= n;i++)
{
if(!vis[i])
a[++len] = i;
for(int j = ;(j <= len )&&(i * a[j] <= n);j++)
{
vis[a[j] * i] = true;
if(!(i % a[j]))
break;
}
}
printf("%d",len);
return ;
}
要说保证某数不被重复判断，关键就在这行代码上。
满足上式时，i是pri[j]的倍数，那么对于后面的pri[k]来说，i * pri[k]就可以被分解为pri[j] * (i / pri[j] *pri[k])，而该数在之前i == pri[j]的时候已经出现过，于是就重复了。直接退出，避免了重复判定。
欧拉筛法固然快，但是也有适用条件，例如求(n, n + 10)中的素数个数的时候，它就明显慢了。由于必须从1开始，所以欧拉筛法的用处在于直接打表而不是求某一段区间。对于这种问题，朴素法未尝不可。
欧拉筛法的原理分析至此结束。
------=====-----=====-----====-----======-------=========================================================
埃氏筛法：
从2开始把素数的倍数都给标记掉，复杂度为 O(nlog(logn)) 。
欧拉筛法：
把2压到栈/队列中，外面的数可以被栈/队列中的数整除的话，丢掉，不能的话，压入栈/队列中。
以6为例：
埃氏筛法会遍历到他很多遍
欧拉筛法只会遍历一遍