检验一个数是否是素数，朴素的方法有试除法，筛法，因为费马小定理和模的运算，可以将时间复杂度降为klogN，k是常数，k越大，算法返回结果正确的概率越高
费马小定理
a^(p-1)≡1 (mod p)（a不是p的倍数）
费马小定理的逆定理不一定成立，即可能是合数也返回了1，这样的数称为伪素数，但a不同的取值会让错误得到修正，重新返回正确结果，任选一个在2~n-1的数，会出现错误的概率不会超过1/2，取十次错误率不到千分之一，所以是具有有效性的。
同余运算：
1、(a±b)%p=(a%p±b%p)%p
2、(ab)%p=(a%pb%p)%p
3、同余式相加减a≡b(mod m) c≡d(mod m) => a±b≡b±d(mod m)
高指数的同余运算利用同余的性质，把余数不断幂乘
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
typedef long long ll;
ll Quick_Mod(ll a, ll b, ll mod)//快速幂 a^b%mod
{
ll res = 1,term = a % mod;
while(b)
{
if(b & 1) res = (res * term) % mod;//取b的最后一位，若是1，执行
term = (term * term) % mod;//幂乘
b >>= 1;//b变为原来1/2
}
return res;
}
bool Is_Prime(ll N)
{
srand(time(0));
int i;//随机取10个数
for (i = 0; i < 10; i++) {
if (Quick_Mod(1 + rand() % (N - 1), N - 1, N)!=1) {
break;
}
}
if (i < 10)return false;
else return true;
}