fork(3) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4. #define M 1000000000
  5. ll pro(ll a,ll b,ll n)
  6. {
  7.     if(a<M && b<M)
  8.         return (a*b)%n;
  9.     if(b==0 || a==0)
  10.         return 0;
  11.     if(b==1)
  12.         return a%n;
  13.     else if(b%2==0)
  14.         return pro((a+a)%n,b/2,n);
  15.     else if(b%2==1)
  16.         return (a+pro((a+a)%n,b/2,n))%n;
  17. }
  18. ll bit(ll p,ll q,ll mod)
  19. {
  20.     ll r=1;
  21.     while(q>0)
  22.     {
  23.         if(q&1)
  24.             r=pro(r,p,mod);
  25.         q=q>>1,p=pro(p,p,mod);
  26.     }
  27.     return r;
  28. }
  29. int test(ll n,ll d,int r)
  30. {
  31.     ll y,a=rand()%(n-4)+2;
  32.     y=bit(a,d,n);
  33.     if(y==1 || y==n-1)
  34.         return 1;
  35.     while(r>1)
  36.     {
  37.         y=pro(y,y,n),r--;
  38.         if(y==1)
  39.             return 0;
  40.         else if(y==n-1)
  41.             return 1;
  42.     }
  43.     return 0;
  44. }
  45. int mill(ll n,int k)
  46. {
  47.     if(n==1)return 0;
  48.     else if(n<=3)return 1;
  49.     else if(n%2==0)return 0;
  50.     else
  51.     {
  52.         int i,r=0;
  53.         ll d=n-1;
  54.         while(d%2==0)d/=2,r++;
  55.         for(i=0;i<k;i++)
  56.         {
  57.             if(test(n,d,r)==0)
  58.                 return 0;
  59.         }
  60.         return 1;
  61.     }
  62. }
  63. int main()
  64. {
  65.     ll n;
  66.     cin >> n;
  67.     int x=mill(n,4);
  68.     cout << x << endl;
  69. }
  70.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/9qDVjx
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!