就存个板子吧: 具体想学算法的可以看其他博客.....
- #include <bitset>
- #include <cstring>
- #include <algorithm>
- #include <iostream>
- #include <cstdio>
- #include <cmath>
- using namespace std;
- typedef long long LL;
- LL mul(LL a, LL b, LL p)
- {
- LL rn=0, i;
- for(i=1; i<=b; i<<=1,a=(a+a)%p)
- if(b&i) rn=(rn+a)%p;
- return rn;
- } // 计算模意义下两大数乘积
- LL ksm(LL a, LL b, LL p)
- {
- LL rn=1;
- for(; b; a=mul(a,a,p),b>>=1)
- if(b&1) rn=mul(rn,a,p);
- return rn;
- } // 计算模意义下两大数乘方
- LL gcd(LL a, LL b)
- {
- LL tmp; if(a<b) tmp=a,a=b,b=tmp;
- while(b) tmp=a%b, a=b, b=tmp;
- return a;
- } // 求最大公约数
- bool isprime(LL n)
- {
- if(n==2) return true;
- //n==2 的时候直接判断
- if(n<2 || !(n&1)) return false;
- //n 为偶数或者 n 等于 2 为错误
- LL a,x,y, u=n-1; int t=0;
- while((u&1)==0) t++, u>>=1;
- // 将 (p-1) 拆成 k*(2^j), 先令 x=(p-1)^k, 对于 2^j
- // 我们一边平方 x, 一边利用定理 2 判定
- // 最后用定理 1 检查一次
- for(int i=0; i<10; i++)
- {
- a=rand()%(n-1)+1;
- // 随机一个数
- x=ksm(a,u,n);
- // 将 x 乘以 2 倍, 为什么要这样搞, 是为了防止 long long * long long 爆掉
- for(int j=1; j<=t; j++)
- {
- y=mul(x,x,n);
- // 二次检测
- if(y==1 && x!=1 && x!=n-1) return false;
- // 是否通过二次检测
- x=y;
- }
- if(x!=1) return false;
- // 最后再试一遍
- }
- return true;
- }
- int main(){
- int n,ans=0;
- LL x;
- while(scanf("%d",&n)!=EOF) {
- ans=0;
- while (n--) {
- scanf("%lld", &x);
- if (isprime(x)) ans++;
- }
- printf("%d\n", ans);
- }
- }
- View Code
[pandaking 训练 7]----- 基础数论 c 题 hdu2138 miller-robbin 判断素数
来源: http://www.bubuko.com/infodetail-3111668.html