fork(1) download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. /* This function calculates (ab)%c */
  5. int modulo(int a,int b,int c)
  6. {
  7.     long long x=1,y=a; // long long is taken to avoid overflow of intermediate results
  8.     while(b > 0)
  9.     {
  10.         if(b%2 == 1)
  11.         {
  12.             x=(x*y)%c;
  13.         }
  14.         y = (y*y)%c; // squaring the base
  15.         b /= 2;
  16.     }
  17.     return x%c;
  18. }
  19.  
  20. /* this function calculates (a*b)%c taking into account that a*b might overflow */
  21. long long mulmod(long long a,long long b,long long c)
  22. {
  23.     long long x = 0,y=a%c;
  24.     while(b > 0)
  25.     {
  26.         if(b%2 == 1)
  27.         {
  28.             x = (x+y)%c;
  29.         }
  30.         y = (y*2)%c;
  31.         b /= 2;
  32.     }
  33.     return x%c;
  34. }
  35.  
  36. /* Miller-Rabin primality test, iteration signifies the accuracy of the test */
  37. bool Miller(long long p,int iteration)
  38. {
  39.     if(p<2)
  40.     {
  41.         return false;
  42.     }
  43.     if(p!=2 && p%2==0)
  44.     {
  45.         return false;
  46.     }
  47.     long long s=p-1;
  48.     while(s%2==0)
  49.     {
  50.         s/=2;
  51.     }
  52.     for(int i=0; i<iteration; i++)
  53.     {
  54.         long long a=rand()%(p-1)+1,temp=s;
  55.         long long mod=modulo(a,temp,p);
  56.         while(temp!=p-1 && mod!=1 && mod!=p-1)
  57.         {
  58.             mod=mulmod(mod,mod,p);
  59.             temp *= 2;
  60.         }
  61.         if(mod!=p-1 && temp%2==0)
  62.         {
  63.             return false;
  64.         }
  65.     }
  66.     return true;
  67. }
  68.  
  69. int main()
  70. {
  71.     long long int n,p;
  72.     int cas=1;
  73.  
  74.     int t;
  75.     cin>>t; // test case
  76.  
  77.     while(t--)
  78.     {
  79.         cin>>n; //given number n
  80.  
  81.         if(n==1|| n==0)
  82.             printf("Case %d: 2\n",cas++);
  83.  
  84.         else if(Miller(n,20))           //if the number prime print it
  85.             printf("Case %d: %lld\n",cas++,n);
  86.  
  87.         else
  88.         {
  89.             for(int i=1; i<n; i++)
  90.                 if(Miller((n+i),20))
  91.                 {
  92.                     printf("Case %d: %lld\n",cas++,n+i);
  93.                     break;
  94.                 }
  95.         }
  96.  
  97.     }
  98.  
  99.     return 0;
  100.  
  101. }
  102.  
Time limit exceeded #stdin #stdout 5s 3344KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/GrCsy5
language:
C++14 (gcc 8.3)
created:
10 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!