ZSTU3794-Next Prime

http://acmpj.zstu.edu.cn/JudgeOnline/showproblem?problem_id=3794

大数的素数判断很吊的样子，现在这里记录一下吧- -当初水过去了。。。

#include
#include
using namespace std;
long long factor[100],fac_top=-1;
long long muti_mod(long long a,long long b,long long n)
{long long exp=a%n,res=0;while(b){if(b&1){res+=exp;if(res>n) res-=n;}exp<<=1;if(exp>n) exp-=n;b>>=1;}return res;
}
long long mod_exp(long long a,long long p,long long m)
{long long exp=a%m,res=1;   while(p>1){if(p&1)res=muti_mod(res,exp,m);exp=muti_mod(exp,exp,m);p>>=1;}return muti_mod(res,exp,m);
}
bool miller_rabin(long long n, long long times)
{if(n==2)return 1;if(n<2||!(n&1))return 0;long long a,u=n-1,x,y;int t=0;while(u%2==0){t++;u/=2;}srand(time(0));for(int i=0;i){a=rand()%(n-1)+1;x=mod_exp(a,u,n);for(int j=0;j){y=muti_mod(x,x,n);if(y==1&&x!=1&&x!=n-1)return false;x=y;}if(y!=1) return false;}return true;
}
int main(void)
{long long t,n,min;cin>>t;while(t--){cin>>n;fac_top=min=-1;while(!miller_rabin(n,10))miller_rabin(n++,10);cout<endl;}return 0;
}

转载于:https://www.cnblogs.com/YogurtShen/archive/2012/08/29/2661852.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！