safe保险一点5吧。我是MR：
1 const int Safe=3; 2 int gcd(int a,int b){return !b?a:gcd(b,a%b);} 3 int mul(int a,int b,int p){ 4 int tmp=(a*b-(int)((double)a/p*b+1e-8)*p); 5 return tmp<0?tmp+p:tmp; 6 } 7 int pow(int a,int b,int p){ 8 int ans=1;a%=p; 9 for(int i=b;i;i>>=1,a=mul(a,a,p)) 10 if(i&1)ans=mul(ans,a,p); 11 return ans; 12 } 13 bool check(int a,int n,int r,int s){ 14 int ans=pow(a,r,n),p=ans; 15 for(int i=1;i<=s;i++){ 16 ans=mul(ans,ans,n); 17 if(ans==1&&p!=1&&p!=n-1) return true; 18 p=ans; 19 } if(ans!=1)return true;return false; 20 } 21 bool MR(int n){ 22 if(n<=1) return false; 23 if(n==2) return true; 24 if(!(n&1)) return false; 25 int r=n-1,s=0; 26 while(!(r&1)) r>>=1,s++; 27 for(int i=0;i<Safe;i++) 28 if(check(rand()%(n-1)+1,n,r,s)) return false; 29 return true; 30 }
我是rho：
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #include <cstring> 5 #include <cmath> 6 #define ll long long 7 #define inf 1000000000 8 #define Safe 5 9 using namespace std; 10 ll gcd(ll a, ll b){ 11 return b == 0 ? a : gcd(b, a % b); 12 } 13 ll n, x, mx; 14 ll mul(ll a, ll b, ll p){ 15 ll tmp = (a * b - (ll)((long double)a / p * b + 1e-8) * p); 16 return tmp < 0 ? tmp + p : tmp; 17 } 18 ll pow(ll a, ll b, ll p){ 19 ll ans = 1; a %= p; 20 for(ll i = b; i; i >>= 1, a = mul(a, a, p)) 21 if(i & 1) ans = mul(ans, a, p); 22 return ans; 23 } 24 bool check(ll a, ll n, ll r, ll s){ 25 ll ans = pow(a, r, n), p = ans; 26 for(int i = 1; i <= s; i ++){ 27 ans = mul(ans, ans, n); 28 if(ans == 1 && p != 1 && p != n - 1) return true; 29 p = ans; 30 } 31 if(ans != 1)return true; 32 return false; 33 } 34 bool MR(ll n){ 35 if(n <= 1) return false; 36 if(n == 2) return true; 37 if(n % 2 == 0) return false; 38 ll r = n - 1, s = 0; 39 while(r % 2 == 0) r /= 2, s ++; 40 for(int i = 0; i < Safe; i ++) 41 if(check(rand() % (n - 1) + 1, n, r, s)) return false; 42 return true; 43 } 44 ll rho(ll n, ll c){ 45 ll k = 2, x = rand() % n, y = x, p = 1; 46 for(ll i = 1; p == 1; i ++){ 47 x = (mul(x, x, n) + c) % n; 48 p = y > x ? y - x : x - y; 49 p=gcd(n, p); 50 if(i == k) y = x, k += k; 51 } 52 return p; 53 } 54 void solve(ll n){ 55 if(n == 1) return; 56 if(MR(n)) { mx = max(n, mx); return; } 57 ll t = n; 58 while(t == n) t = rho(n, rand() % (n - 1) + 1); 59 solve(t); solve(n / t); 60 } 61 void read(ll &x){ 62 x = 0; ll sig = 1; char ch = getchar(); 63 while(!isdigit(ch)) { if(ch == '-') sig = -1; ch = getchar(); } 64 while(isdigit(ch)) x = 10 * x + ch - '0', ch = getchar(); 65 x *= sig; return ; 66 } 67 ll cnt = 0; 68 void init(){ 69 read(n); 70 cnt = 0; 71 return ; 72 } 73 void work(){ 74 while(n --){ 75 read(x); 76 if(MR(x)) cnt ++; 77 mx = 0; solve(x); 78 if(mx == x) puts("Prime"); 79 else printf("%lld ", mx); 80 } 81 return ; 82 } 83 void print(){ 84 printf("%lld ", cnt); 85 return ; 86 } 87 int main(){ 88 init(); 89 work(); 90 print(); 91 return 0; 92 }