fork download
copy 
  1. #include<stdio.h>
  2.  
  3. long long ModMultiply(long long a,long long b, long long Mod)   // O(1) for (a*b)%mod
  4. {
  5.     long long div = ((double)a*b /Mod) - 1;
  6.     return (a*b - div*Mod)%Mod;
  7. }
  8.  
  9. inline long long ModPow(long long a, long long b, long long Mod)
  10. {
  11.    long long Ans=1;
  12.    while(b)
  13.    {
  14.        if(b&1)  Ans = ModMultiply(Ans,a,Mod);
  15.        a = ModMultiply(a,a,Mod);
  16.        b>>=1;
  17.    }
  18.    return Ans;
  19. }
  20.  
  21. inline int Miller(long long n, long long iteration)
  22. {
  23.     if( (n<2) || (n!=2 && n%2==0) )  return 0;  // false
  24.     long long d = n-1;
  25.     while(d%2==0)    d >>= 1;
  26.     int i;
  27.     for(i=0; i<iteration; i++)
  28.     {
  29.         long long a = rand()%(n-1) + 1;
  30.         long long temp = d;
  31.         long long x = ModPow(a,temp,n);
  32.         while(temp!=n-1 && x!=1 && x!=n-1)
  33.         {
  34.             x = ModMultiply(x,x,n);
  35.             temp <<= 1;  // temp*=2
  36.         }
  37.         if (x!=n-1 && temp%2==0)
  38.         return 0;
  39.     }
  40.   return 1;
  41. }
  42.  
  43. int main()
  44. {
  45.     int T;
  46.     long long i,N;
  47.     scanf("%d",&T);
  48.     while(T--)
  49.     {
  50.         scanf("%lld",&N);
  51.         if(N == 2 || N == 3)  {  printf("%lld\n",N);  continue; }
  52.         for(i=N;  ; i--)
  53.         {
  54.             if( Miller(i,2) )  {  printf("%lld\n",i);  break;  }
  55.         }
  56.     }
  57.   return 0;
  58. }
Success #stdin #stdout 0s 1840KB
comments (?)
stdin
copy 
3
2
3
4
stdout
copy 
2
3
3
https://ideone.com/hFGQPq
language:
C (gcc 8.3)
created:
11 years ago
visibility:
secret

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!