所谓素数，是指恰好有两个约数的正整数。
埃氏筛法
区间筛法
Miller-Rabin素性测试
判定单一的一个数是不是素数，素性测试：
bool is_prime(int n){ /* 判定一个数是不是素数 ，假设输入的数都是正整数 */
for (int i = 2; i * i <= n; i++) {
if (!(n % i)) return false;
}
return n != 1; /* 1是例外 */
}如果只对一个数进行素数测试，通常
Miller-Rabin素性测试
引理1(费马定理) 设p是素数，a为整数，且(a,p)=1，则
引理2(二次探测定理) 如果p是一个素数，且
证明：易知
因为p是质数
虽然Wilson定理（对于给定的正整数n，n是素数的充要条件为
首先我们要知道费马定理只是n是素数的必要条件。即费马定理不成立，n一定是合数；费马定理成立，n可能是素数。
假设n是奇素数，则
随机选取整数
由二次探测定理可知：
若
所以该算法的过程为
给定奇数n，为了判断是否为素数，首先测试
考察下面的Miller序列：
若
可以证明 Miller-Rabin 算法给出错误结果的概率小于等于
const int S = 8;
LL mult_mod(LL a, LL b, LL c){
a %= c;
b %= c;
LL ret = 0;
LL tmp = a;
while(b){
if(b&1){
ret += tmp;
if(ret > c) ret -= c;
}
tmp <<= 1;
if(tmp > c) tmp -= c;
b >>= 1;
}
return ret;
}
LL pow_mod(LL a, LL n, LL mod){
LL ret = 1;
LL temp = a % mod;
while(n){
if(n & 1) ret = mult_mod(ret, temp, mod);
temp = mult_mod(temp, temp, mod);
n >>= 1;
}
return ret;
}
bool check(LL a, LL n, LL x, LL t){
LL ret = pow_mod(a, x, n);
LL last = ret;
loop(i, 1, t){
ret = mult_mod(ret, ret, n);
if(ret == 1 && last != 1 && last != n-1) return true;
last = ret;
}
if(ret != 1) return true;
else return false;
}
bool Miller_Rabin(LL n){
if(n < 2) return false;
if(n == 2) return true;
if((n&1)==0) return false;
LL x = n-1;
LL t = 0;
while((x&1)==0){x >>= 1; ++t;}
srand(time(NULL));
rep(i, S){
LL a = rand()%(n-1)+1;
if(check(a, n, x, t)) return false;
}
return true;
}埃氏筛法
要枚举n以内的素数，可以用埃氏筛法：这是一种古老的算法，首先，将2到n范围内的所有整数写下来。其中最小的数字2是素数。将表中所有2的倍数都划去，然后表中剩余最小的素数是3，将表中所有3的倍数也都划去。以此类推，如果表中剩余最小的素数是m的话，就将表中所有m的倍数都划去，像这样反复操作，就能依次枚举n以内的素数，埃氏筛法的时间复杂度仅有
bool is_prime[100];
int prime[100];
int sieve(int n) { /* 枚举n以内的素数 */
/* 返回n以内素数的个数，素数存在prime数组里 */
int p = 0;
for (int i = 0; i <= n; i++)
is_prime[i] = true;
is_prime[0] = is_prime[1] = false;
for (int i = 2; i <= n; i++) {
if (is_prime[i]) {
prime[p++] = i;
for (int j = i * 2; j <= n; j += i)
is_prime[j] = false;
}
}
return p;
}区间筛法
目的： 找出a~b这个区间有几个质数，哪些是质数
做法： 在筛出[0,sqrt(b)之间的素数的同时，将在[a,b)这个区间的之中的该素数的倍数都划掉。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define M 100000000
typedef long long ll;
bool is_prime_small[M];
bool is_prime[M];
ll ans = 0;
void prime(ll a, ll b) {
for (ll i = 2; i * i < b; i++) is_prime_small[i] = true; //初始化2~b^(1/2)
for (ll i = 0; i < b - a; i++) is_prime[i] = true; //因为a,b很大，所以用0~b-a 代表a~b
for (ll i = 2; i * i < b; i++) {
if (is_prime_small[i]) {
for (ll j = 2 * i; j * j < b; j += i) is_prime_small[j] = false;
for (ll j = max(2LL, (a + i - 1) / i) * i; j < b; j += i) { //找到从a开始的第一个合数
if (is_prime[j - a]) {
ans++; //求出几个合数。 //或者也可以最后遍历b-a这区间，求出质数的个数。
is_prime[j - a] = false;
}
}
}
}
}
int main() {
ll a, b;
ans = 0;
cin >> a >> b;
prime(a, b);
// for(ll i = 0;i < b-a;i++)
// if(is_prime[i]) ans++;
cout << "ans = " << b - a - ans << endl;
return 0;
}例题
#include <iostream>
#include <cstdio>
#include <algorithm>
#define M 1000001
using namespace std;
int num[M];
int is_prime[M];
int ans[M];
void slove() {
for (int i = 0; i < M; i++) is_prime[i] = true;
int k = 1;
num[1] = 0;
is_prime[1] = true;
for (int i = 2; i < M; i++) {
if (is_prime[i]) {
num[i] = k++;
ans[i] = num[i];
for (int j = 2 * i; j < M; j += i) {
is_prime[j] = false;
ans[j] = num[i];
}
}
}
}
int main() {
slove();
int a;
while (scanf("%d", &a) == 1) {
printf("%d\n", ans[a]);
}
return 0;
}