首页 > 代码库 > poj1811 Prime Test,随机素数测试
poj1811 Prime Test,随机素数测试
Prime Test
Time Limit: 6000MS | Memory Limit: 65536K | |
Total Submissions: 24514 | Accepted: 5730 | |
Case Time Limit: 4000MS |
Description
Given a big integer number, you are required to find out whether it‘s a prime number.
Input
The first line contains the number of test cases T (1 <= T <= 20 ), then the following T lines each contains an integer number N (2 <= N < 254).
Output
For each test case, if N is a prime number, output a line containing the word "Prime", otherwise, output a line containing the smallest prime factor of N.
Sample Input
2 5 10
Sample Output
Prime 2
Miller_Rabin 算法
#include <cstdio> #include <cstring> #include <cmath> #include <ctime> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; // rand(void)返回一个[0,RAND_MAX]之间的随机整数。 //random(n) 返回一个[0,n]之间的随机整数 ll random(ll n) { return (ll)((double)rand()/RAND_MAX*n + 0.5); } inline ll mul_mod(ll a, ll b, ll c) { ll res = 0; a %= c; b %= c; for(; b; b>>= 1, a=(a<<1)%c) { if(b&1) res = (res+a)%c; } return res; } ll pow_mod(ll a, ll b, ll c) { ll res = 1; for(; b; b>>=1, a=mul_mod(a,a,c)) { if(b&1) res = mul_mod(res, a, c); } return res; } bool check(ll a, ll n, ll x, ll t) { ll ret = pow_mod(a, x, n); ll last = ret; for(int i=1; i<=t; ++i) { ret = mul_mod(ret, ret, n); if(ret==1 && last!=1 && last!=n-1) return true; last = ret; } if(ret!=1) return true; else return false; } const int N = 8; bool miller_rabin(ll n) { if(n<2) return false; if(n==2) return true; if( (n&1)==0) return false; ll x = n-1; ll t = 0; while( (x&1)==0 ) { x >>= 1; t++; } for(int i=0; i< N; ++i) { ll a = random(x-2) + 1; if( check(a,n,x,t) ) return false; } return true; } ll factor[100]; int tol; ll gcd(ll a, ll b) { return b?gcd(b,a%b): a>=0?a:-a; } ll pollard_rho(ll x, ll c) { ll i=1, k=2; ll x0 = random(x-2) + 1; ll y = x0; while(1) { i++; x0 = (mul_mod(x0,x0,x) + c) % x; ll d = gcd(y-x0, x); if(d != 1 && d != x) return d; if(y == x0) return x; if(i == k) { y = x0; k += k; } } } void findfac(ll n, int k) { if(n==1) return ; if(miller_rabin(n)) { factor[tol++] = n; return ; } ll p = n; int c = k; while(p >= n) p = pollard_rho(p, c--); findfac(p, k); findfac(n/p, k); } int main() { int T; ll n; // srand(time(NULL)); //POJ上G++要去掉这句话,一个忧伤的故事。。 scanf("%d", &T); while(T--) { scanf("%lld", &n); if(miller_rabin(n)) { printf("Prime\n"); } else { tol = 0; findfac(n, 107); ll ans = factor[0]; for(int i=1; i<tol; ++i) if(ans > factor[i]) ans = factor[i]; printf("%lld\n", ans); } } return 0; }
poj1811 Prime Test,随机素数测试
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。