数论-素数

判定素数

穷举法判定

orz

1
2
3
4
5
6
7
8
bool check(int k)
{
if(k==0||k==1)return false;
for(int i=2;i<=sqrt(k);i++)
if(k%i==0)
return false;
return true;
}

埃氏筛法

1
2
3
4
5
6
7
8
9
10
void make_primetable(int n)
{
memset(is_prime,true,sizeof(is_prime));
is_prime[0]=false;
is_prime[1]=false;
for(int i=2;i<=n;i++)
if(is_prime[i])
for(int j=i*i;j<=n;j++)
is_prime[j]=true;
}

线性筛法

数学一本通的线性筛是错的!!看了我好久!!
这里写图片描述

埃氏筛法里面很多合数都会被重复筛选。我们为了避免这个情况出现,就有了线性筛法,线性筛法没有冗余,所以几乎是线性的算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#define maxn 10000005
bool is_not_prime[maxn];
int prime[maxn],num_prime;
void get_prime(int n)
{
for(int i=2;i<=n;i++)//从2到n
{
if(!is_not_prime[i])
prime[num_prime++]=i;
//如果i是质数,那么就把它保存在一个素数表里面。
for(int j=0;j<num_prime&&i*prime[j]<=n;j++)
{
is_not_prime[i*prime[j]]=true;
if(!(i%prime[j]))//避免重复筛选的剪枝
break;
}
}
}

Miller-Rabin素数测试

数论学家利用费马小定理研究出了多种素数的测试方法。Miller-Rabin就是其中一种。
费马小定理的证明在这里
我们先来说几个概念:
伪素数:如果$n$是一个正整数,如果存在和$n$互质的正整数$a$满足$a^{n-1}\equiv 1\pmod n$,我们说$n$是基于$a$的伪素数。如果一个数是伪素数,那么它几乎肯定是素数(这句话的意思是,一个随机数$a$去测试数$n$,如果通过测试了,它就是一个伪素数,是素数的可能性就很大了)
Miller-Rabin算法的本质就是反复应用这个结论,把某一个数通过测试的概率累乘,那么这个数是素数的概率就接近$100\%$。
如果测试次数是$t$,如果$t$次测试全部通过,那么这个数是素数的概率是$4^{-t}$。
时间复杂度是$t\times log_3n$

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int num=0;
char c=' ';
bool flag=true;
for(;c>'9'||c<'0';c=getchar())
if(c=='-')
flag=false;
for(;c>='0'&&c<='9';num=num*10+c-48,c=getchar());
return flag ? num : -num;
}
const int times=100;//测试次数

int modular_exp(int a,int m,int n)
{
if(m==0)return 1;
if(m==1)return (a%n);
long long w=modular_exp(a,m/2,n);
w=w*w%n;
if(m&1)w=w*a%n;
return w;
}

bool Miller_Rabin(int n)
{
if(n==2)return true;
if(n==1||n==0)return false;
for(int i=1;i<=times;i++)
{
int a=rand()%(n-2)+2;
if(modular_exp(a,n-1,n)!=1)return false;
}
return true;
}
int main()
{
srand(time(NULL));
int n=read();
int m=read();
for(int i=1;i<=m;i++)
{
int x=read();
if(Miller_Rabin(x))
printf("Yes\n");
else
printf("No\n");
}
return 0;
}

文章目录
  1. 1. 判定素数
    1. 1.1. 穷举法判定
    2. 1.2. 埃氏筛法
    3. 1.3. 线性筛法
    4. 1.4. Miller-Rabin素数测试