SHARE
TWEET

miller_rabin

RaFiN_ Apr 25th, 2019 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2.  
  3. i128 mul(i128 a,i128 b,i128 m){
  4.     i128 ans = 0;
  5.     while(b){
  6.         ///cout<<a<<" "<<b<<" "<<m<<endl;
  7.         if(b&1)ans = (ans + a)%m;
  8.         a = (a+a)%m;
  9.         b>>=1;
  10.     }
  11.     return ans;
  12. }
  13.  
  14. i128 power(i128 base,i128 p,i128 m){
  15.     ///cout<<base<<" "<<p<<" "<<m<<endl;
  16.     if(p==0)return 1;
  17.     if(p&1)return (base % m * power(base,p-1,m) % m)%m;
  18.     else {
  19.         i128 x = power(base,p/2,m)%m;
  20.         return mul(x,x,m)%m;
  21.     }
  22.  
  23. }
  24.  
  25.  
  26. bool miller_rabin(i128 p,i128 d){
  27.  
  28.     i128 a = rand() %(p-4) + 2;
  29.     i128 x = power(a,d,p);
  30.     if(x==1||x==p-1)return true;
  31.     while(d!=p-1){
  32.         x = mul(x,x,p)%p;
  33.         d = d*2;
  34.         if(x==1)return false;
  35.         if(x==p-1)return true;
  36.  
  37.     }
  38.     return false;
  39. }
  40.  
  41. bool isPrime(i128 n){
  42.     if(n<=1||n==4)return false;
  43.     if(n<=3)return true;
  44.     i128 d = n-1;
  45.     while(d%2==0){
  46.         d/=2;
  47.     }
  48.     for(int i = 0;i<4;i++)if(!miller_rabin(n,d))return false;
  49.     return true;
  50. }
  51.  
  52.  
  53. int main()
  54. {
  55.     //booster()
  56.     ///read("input.txt");
  57.     int t;
  58.     scani(t);
  59.  
  60.     while(t--){
  61.         ll x;
  62.  
  63.         scanf("%lld",&x);
  64.         if(isPrime(x))puts("prime");
  65.         else puts("composite");
  66.  
  67.  
  68.     }
  69.  
  70.     return 0;
  71. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top