fork(3) download
copy 
  1. #include <iostream>
  2. #include <cmath>
  3.  
  4. using namespace std;
  5.  
  6.  unsigned long long int mul(unsigned long long int a, unsigned long long int b, unsigned long long int mod)
  7.     {
  8.         int i;
  9.         unsigned long long int now = 0;
  10.         for (i = 63; i >= 0; i--) if (((a >> i) & 1) == 1) break;
  11.         for (; i >= 0; i--)
  12.         {
  13.             now <<= 1;
  14.             while (now > mod) now -= mod;
  15.             if (((a >> i) & 1) == 1) now += b;
  16.             while (now > mod) now -= mod;
  17.         }
  18.         return now;
  19.     }
  20.  
  21.     unsigned long long int pow(unsigned long long int a, unsigned long long int p, unsigned long long int mod)
  22.     {
  23.         if (p == 0) return 1;
  24.         if (p % 2 == 0) return pow(mul(a, a, mod), p / 2, mod);
  25.         return mul(pow(a, p - 1, mod), a, mod);
  26.     }
  27.  
  28.  
  29. bool MillerRabin(unsigned long long int n)
  30. {
  31.         int l;
  32.          unsigned long long int ar[9] = { 2, 3, 5, 7, 11, 13, 17, 19, 23 };
  33.         if (n < 4759123141) {
  34.  
  35.                 l = 3;
  36.         }
  37.         else if (n < 341550071728321) {
  38.                 l = 7;
  39.         }
  40.         else {
  41.  
  42.                 l = 9;
  43.         }
  44.         //l = 9;
  45.         unsigned long long d = n - 1;
  46.         int s = 0;
  47.         while ((d & 1) == 0) { d >>= 1; s++; }
  48.         int i, j;
  49.         for (i = 0; i < l; i++)
  50.         {
  51.             unsigned long long int a  = min(n - 2, ar[i]);
  52.             unsigned long long int now = pow(a, d, n);
  53.             if (now == 1) continue;
  54.             if (now == n - 1) continue;
  55.             for (j = 1; j < s; j++)
  56.             {
  57.                 now = mul(now, now, n);
  58.                 if (now == n - 1) break;
  59.             }
  60.             if (j == s) return false;
  61.         }
  62.         return true;
  63.     }
  64.  
  65.     bool check_prime(unsigned long long int n) {
  66.  
  67.     if(!MillerRabin(n)) return false;
  68.     if(n == 2) return true;
  69.     if(n % 2 == 0) return false;
  70.     for(unsigned long long int i = 3; i <= sqrt(n); i+=2) {
  71.         if(n % i == 0) return false;
  72.     }
  73.     return true;
  74. }
  75.  
  76. int main()
  77. {
  78.     int t;
  79.  
  80.     cin >> t;
  81.  
  82.     while(t--) {
  83.         unsigned long long int n;
  84.         cin >> n;
  85.         while(1) {
  86.             if(check_prime(n)) {
  87.                 cout << n << endl;
  88.                 break;
  89.             }
  90.             else {
  91.                 n--;
  92.             }
  93.         }
  94.     }
  95.  
  96. }
  97.  
Success #stdin #stdout 0s 2860KB
comments (?)
stdin
copy 
1
10000000
stdout
copy 
9999991
https://ideone.com/ksLwRk
language:
C++ (gcc 8.3)
created:
12 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!