##### 题目描述 在算法竞赛中你会遇到各种各样的有关素数的问题，今天你来解决一个最基础的问题：如何判定一个素数。 对于给定的正整数p，若p非素数，输出-1 若p是素数 输出 ：{sigma(a^(p-1) % p) ，其中a的下界为1，上界为p-1} 即： ~~~[math] \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就是一个质数。 一般情况下，我们只需要列举十个左右的数字即可确定一个数字是否为质数。 代码如下： ~~~ #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; } ~~~ 用以上方法即可迅速判断一个数是否是质数，对特别大的数字尤其适用。