1 #include<cstdio>  2 #include<algorithm>  3 using namespace std;  4 typedef __int64 LL;  5 LL mulmod(LL a,LL b,LL c) { //ret=(a*b)%c  6     LL ret=0;  7     for(; b; a=(a<<1)%c,b>>=1) {  8         if(b&1) {  9             ret=(ret+a)%c; 10         } 11     } 12     return ret; 13 } 14 LL powmod(LL a,LL b,LL c) { //ret=(a^b)%mod 15     LL ret=1%c; 16     for(; b; a=mulmod(a,a,c),b>>=1) { 17         if(b&1) { 18             ret=mulmod(ret,a,c); 19         } 20     } 21     return ret; 22 } 23 bool suspect(LL a,int s,LL d,LL n) { 24     LL x=powmod(a,d,n); 25     if(x==1) return true; 26     while(s--) { 27         if(x==n-1) return true; 28         x=mulmod(x,x,n); 29     } 30     return false; 31 } 32 const int test[]= {2,3,5,7,11,13,17,19,23,-1}; // for n < 10^16 33 bool isprime(LL n) { //Miller-Rabin 大素数测试 34     if(n<=1||(n>2&&(!(n&1)))) return false; 35     LL d=n-1; 36     int s=0; 37     while(!(d&1)) { 38         s++; 39         d>>=1; 40     } 41     for(int i=0; test[i]<n&&~test[i]; i++) { 42         if(!suspect(test[i],s,d,n)) return false; 43     } 44     return true; 45 } 46 LL gcd(LL a,LL b){//最大公约数 47     return b?gcd(b,a%b):a; 48 } 49 LL pollard_rho(LL n,LL c){//Pollard-Rho 找到n的一个约数 50     LL d,x=rand()%n,y=x; 51     for(LL i=1,k=2;;i++){ 52         x=(mulmod(x,x,n)+c)%n; 53         d=gcd(y-x,n); 54         if(d>1&&d<n) return d; 55         if(x==y) return n; 56         if(i==k){ 57             y=x; 58             k<<=1; 59         } 60     } 61     return 0; 62 } 63 LL factor[128];//质因素分解结果（刚返回时时无序的） 64 int flen;//质因素的个数，编号0~tol-1 65 void findfac(LL n,int k) { 66     if(n==1) return; 67     if(isprime(n)) { 68         factor[flen++]=n; 69         return ; 70     } 71     LL p=n; 72     int c=k; 73     while(p>=n) { 74         p=pollard_rho(p,c--); 75     } 76     findfac(p,k); 77     findfac(n/p,k); 78 } 79 int main() { 80     int t; 81     LL n; 82     while(~scanf("%d",&t)) { 83         while(t--) { 84             scanf("%I64d",&n); 85             if(isprime(n)) { 86                 puts("Prime"); 87                 continue; 88             } else { 89                 flen=0; 90                 findfac(n,107); 91                 LL ans=factor[0]; 92                 for(int i=1; i<flen; i++) { 93                     ans=min(ans,factor[i]); 94                 } 95                 printf("%I64d\n",ans); 96             } 97         } 98     } 99     return 0;100 }

 1 #include<cstdio> 2 typedef __int64 LL; 3 LL mulmod(LL a,LL b,LL c) { //ret=(a*b)%c 4     LL ret=0; 5     for(; b; a=(a<<1)%c,b>>=1) { 6         if(b&1) { 7             ret=(ret+a)%c; 8         } 9     }10     return ret;11 }12 LL powmod(LL a,LL b,LL c) { //ret=(a^b)%mod13     LL ret=1%c;14     for(; b; a=mulmod(a,a,c),b>>=1) {15         if(b&1) {16             ret=mulmod(ret,a,c);17         }18     }19     return ret;20 }21 bool suspect(LL a,int s,LL d,LL n) {22     LL x=powmod(a,d,n);23     if(x==1) return true;24     while(s--) {25         if(x==n-1) return true;26         x=mulmod(x,x,n);27     }28     return false;29 }30 const int test[]= {2,3,5,7,11,13,17,19,23,-1}; // for n < 10^1631 bool isprime(LL n) { //Miller-Rabin 大素数测试32     if(n<=1||(n>2&&(!(n&1)))) return false;33     LL d=n-1;34     int s=0;35     while(!(d&1)) {36         s++;37         d>>=1;38     }39     for(int i=0; test[i]<n&&~test[i]; i++) {40         if(!suspect(test[i],s,d,n)) return false;41     }42     return true;43 }44 int main(){45     int n,x;46     while(~scanf("%d",&n)){47         int ans=0;48         while(n--){49             scanf("%d",&x);50             if(isprime(x)) ans++;51         }52         printf("%d\n",ans);53     }54     return 0;55 }