费马小定理--轻松判断大质数

题目描述

在算法竞赛中你会遇到各种各样的有关素数的问题,今天你来解决一个最基础的问题:如何判定一个素数。
对于给定的正整数p,若p非素数,输出-1
若p是素数 输出 :{sigma(a^(p-1) % p) ,其中a的下界为1,上界为p-1}

即:

$$
\sum_{a=1}^{p-1}({a^{p-1}\%p})
$$
输入

多实例测试,每组数据包含一个正整数p(p < 10^16)。

输出

根据情况输出一个正整数,保证答案在int64之内,输出占一行。

样例输入

2

样例输出

1

这个题一般方法是就是暴力求解了,首先判断是不是素数,如果不是素数,那么输出-1,如果是素数,那么就实处上面那个式子的值。

但是题目要求的数据范围为1e16,如果我们用一般判断素数的方法(sqrt(n))去求解的话,必定会超时,那么我们如何解决这个问题呢,费马小定理出现了。

费马小定理
假如p是质数,且gcd(a,p)=1,那么 a(p-1)≡1(mod p),例如:假如a是整数,p是质数,则a,p显然互质(即两者只有一个公约数1),那么我们可以得到费马小定理的一个特例,即当p为质数时候, a^(p-1)≡1(mod p)。

因此,我们可以随机几个数字(与p互质),如果a^(p-1)≡1(mod p)对这些数字恒成立,那么p就是一个质数。

一般情况下,我们只需要列举十个左右的数字即可确定一个数字是否为质数。

代码如下:

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n;
ll gcd(ll a,ll b){
return b?gcd(b,a%b):a;
}
ll mulpow(ll a,ll x)
{
ll res=1;
while(x){
if(x&1) res=res*a%n;
a=a*a%n;
x>>=1;
}
return res;
}
int main()
{
ll t,i;
//以下是我自己列举的一些随机数,我们也可以用一些随机数函数来找一些随机数
ll a[20]={7,43,64,69,87,31,45,72,81,79,47,33,43,97,121,199,173,153,157,53};
while(~scanf("%lld",&n)){
for(i=0;i<20;i++){
if(gcd(a[i],n)==1 && mulpow(a[i],n-1)!=1){//两个判断条件,两个数字互质且符合费马小定理
break;
}
}
if(i==20){
printf("%lld\n",n-1);
}
else
printf("-1\n");
}
return 0;
}

用以上方法即可迅速判断一个数是否是质数,对特别大的数字尤其适用。

感谢您的支持
-------------本文结束感谢您的阅读-------------