fork(2) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <chrono>
  4. #include <ctime>
  5. #include <cmath>
  6.  
  7. #define LOG2(X) ((unsigned) (8*sizeof (unsigned long long) - __builtin_clzll((X)) - 1))
  8.  
  9. using namespace std;
  10.  
  11. typedef uint64_t ntype;
  12.  
  13. ////////////////////////////////////////////////////////////////////////////////
  14. struct Task_my
  15. {   ntype result;
  16.     Task_my(ntype from, ntype to)
  17.     {   for(ntype i = from; i <= to; i += 2)
  18.         {   if(is_simple(i)) result = i;
  19.         }
  20.     }
  21.  
  22.     bool is_simple(ntype n)
  23.     {   for(ntype i = 3; i < sqrt(n); i += 2)
  24.         {   if(n%i == 0) return false;
  25.         }
  26.         return true;
  27.     }
  28. };
  29.  
  30. ////////////////////////////////////////////////////////////////////////////////
  31. struct Task_ferma
  32. {   ntype result;
  33.     Task_ferma(ntype from, ntype to)
  34.     {   for(ntype i = from; i <= to; i += 2)
  35.         {   if(ferma(i)) result = i;
  36.         }
  37.     }
  38.  
  39.     bool ferma(ntype x)
  40.     {   if(x == 2) return true;
  41.         srand(time(NULL));
  42.         ntype k = LOG2(x) + 2;
  43.         for(ntype i = 0; i<k; i++)
  44.         {   ntype a = (rand() % (x - 2)) + 2;
  45.             if (gcd(a, x) != 1)        return false;
  46.             if( pows(a, x-1, x) != 1)  return false;
  47.         }
  48.         return true;
  49.     }
  50.     ntype gcd(ntype a, ntype b)
  51.     {   if(b==0) return a;
  52.         return gcd(b, a%b);
  53.     }
  54.     ntype pows(ntype a, ntype b, ntype m)
  55.     {   if(b==0)
  56.             return 1;
  57.         if(b%2==0)
  58.         {   ntype t = pows(a, b/2, m);
  59.             return mul(t , t, m) % m;
  60.         }
  61.         return ( mul(pows(a, b-1, m) , a, m)) % m;
  62.     }
  63.     ntype mul(ntype a, ntype b, ntype m)
  64.     {   if(b==1)
  65.             return a;
  66.         if(b%2==0)
  67.         {   ntype t = mul(a, b/2, m);
  68.             return (2 * t) % m;
  69.         }
  70.         return (mul(a, b-1, m) + a) % m;
  71.     }
  72. };
  73.  
  74. int main() {
  75. 	ntype min_number = 4000000000001ull;
  76.     ntype max_number = 4000000010000ull; 
  77.     ntype cur_number = 1;
  78.     ntype result = 1;
  79.     using time = std::chrono::duration<double, std::milli>;
  80.  
  81.     ////////////////////////////////////////////////////////////////////////////
  82.     auto s3 = std::chrono::high_resolution_clock::now();
  83.     Task_ferma task3(min_number, max_number);
  84.     auto t3 = std::chrono::high_resolution_clock::now() - s3;
  85.  
  86.     cout << "ferma:" << task3.result <<
  87.          " time: " << time(t3).count() << "ms\n";
  88.  
  89.     ////////////////////////////////////////////////////////////////////////////
  90.     auto s2 = std::chrono::high_resolution_clock::now();
  91.     Task_my task2(min_number, max_number);
  92.     auto t2 = std::chrono::high_resolution_clock::now() - s2;
  93.  
  94.     cout << "my:   " << task2.result <<
  95.          " time: " << time(t2).count() << "ms\n";
  96.  
  97.     return 0;
  98. }
Success #stdin #stdout 4.26s 4356KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
ferma:4000000009991 time: 751.001ms
my:   4000000009991 time: 3506.41ms
https://ideone.com/N9Lytw
language:
C++ (gcc 8.3)
created:
5 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!