素数判定_大于4的素数一定是

试除：

bool isprime(int x){
    if(x<=1)return 0;
    for(int i=2;i<=sqrt(x);i++){//i<=sqrt(x)可以改成i*i<=x
        if(x%i==0){
            return 0;
        }
    }
    return 1;
}
1
2
3
4
5
6
7
8
9

利用素数规律加速：

大于4的素数总是等于 6x+1 或 6x-1
（但是6x+1和6x-1不一定是素数噢）

int isPrime(int x) {
    if(x<=3){
        return x>1;//2和3是素数
    }
    if(x%6!=1&&x%6!=5){//不在6x的两边的数一定不是素数
        return 0;
    }
    for(int i=5;i<=sqrt(x);i+=6) { //能整除6x两边的数一定不是素数
        if(x%i==0||x%(i+2)==0){
            return 0; 
        } 
    } 
    return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

筛选法:

埃筛：O(nlogn)

const int maxm=1e7;
int isprime[maxm];//素数筛
int prime[maxm];//素数表
int cnt=0;//计数器
void init(){
    for(int i=2;i<maxm;i++){//初始化为1，标记为素数
        isprime[i]=1;
    }
    for(int i=2;i<maxm;i++){
        if(isprime[i]){
        	prime[cnt++]=i;//加入素数表
            for(int j=i+i;j<maxm;j+=i){//j=i+i可以改成j=i*i
                isprime[j]=0;//标记为非素数
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

缺陷：重复标记，如45=3 * 15=5 * 9，每个45的质因子都把45标记了一遍
其实只需要用最小质因子标记（即后面的欧拉筛）

数据大到1e7以上就不太行了

埃筛的j可以从i*i开始而不是2i，因为之前2i，3i等等已经被筛除了

*基于埃塞思想：

预处理每个数的质因子：

const int maxm=1e7;
vector<int>prime_factor[maxm];
void init(){
    for(int i=2;i<maxm;i++){
        if(prime_factor[i].size()==0){//如果是素数
            for(int j=i;j<maxm;j+=i){
                prime_factor[j].push_back(i);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11

预处理每个数的所有因子：

const int maxm=1e7;
vector<int>factor[maxm];
void init(){
    for(int i=2;i<maxm;i++){
        for(int j=i;j<maxm;j+=i){
            factor[j].push_back(i);
        }
    }
}
1
2
3
4
5
6
7
8
9

预处理每个数的质因数分解：

const int maxm=1e7;
vector<int>prime_factor[maxm];
void init(){
    for(int i=2;i<maxm;i++){
        if(prime_factor[i].size()==0){
            for(int j=i;j<maxm;j+=i){
                int temp=j;
                while(temp%i==0){
                    prime_factor[j].push_back(i);
                    temp/=i;
                }
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

欧拉筛：O(n)

每个数只被最小质因子标记

const int maxm=1e7;
int isprime[maxm];//素数筛
int prime[maxm];//素数表
int cnt=0;//计数器
void init(){
    for(int i=2;i<maxm;i++){//初始化为1，标记为素数
        isprime[i]=1;
    }
    for(int i=2;i<maxm;i++){
        if(isprime[i]){
            prime[cnt++]=i;
        }
        for(int j=0;j<cnt&&prime[j]*i<maxm;j++){
            isprime[prime[j]*i]=0;//素数的倍数标记为非素数
            if(i%prime[j]==0)break;//看外面解释
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

代码里面break的原因：
当i是prime[j]的整数倍时，假设d=i/prime[j]，
那么 i * prime[j+1]等于d * prime[j] * prime[j+1])，即（d * prime[j+1]）* prime[j]
则 i * prime[j+1] 是 prime[j] 的整数倍，在之后会被 prime[j] * 更大的 i 标记。
这样就能保证每个数都只被他的最小质因子标记。

判断大素数：

筛选法+试除法：

O(√n)

要判断n是否是素数
先用筛选法筛选出(2~√n)的素数筛isprime[]和素数表prime[]
n是素数当且仅当isprime[n]==1或者n不能被prime[]中任何数整除

原理：一个数如果有因子，那么肯定有小于等于sqrt(n)的因子
则一个合数分解质因数之后，他的最小质因子一定在sqrt(n)内，
如果sqrt(n)以内的所有质数都不是他的最小质因子，那么他一定是素数

const int maxm=1e7;
int isprime[maxm];//素数筛
int prime[maxm];//素数表
int cnt=0;//计数器
void init(){//先欧拉筛打表
    for(int i=2;i<maxm;i++){//初始化为1，标
        isprime[i]=1;
    }
    for(int i=2;i<maxm;i++){
        if(isprime[i]){
            prime[cnt++]=i;
        }
        for(int j=0;j<cnt&&prime[j]*i<maxm;j++){
            isprime[prime[j]*i]=0;
            if(i%prime[j]==0)break;
        }
    }
}
bool judge(int x){//判断是否是素数，需要的话改int为longlong
    if(x<maxm){
        return isprime[x];
    }else{
        for(int i=0;i<cnt;i++){
            if(x%prime[i]==0){
                return 0;
            }
        }
        return 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

Miller-Rabin测试：