fork download
copy 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int gcd(int u, int v, int &num_iterations)
  6. {
  7.    num_iterations++;
  8.  
  9.    if (v==0)
  10.      return u;
  11.    else
  12.      return gcd(v, u%v, num_iterations);
  13. }
  14.  
  15. int gcd_slow(int u, int v, int &num_iterations)
  16. {
  17.    int low = min(u,v);
  18.    int high = max(u,v);
  19.  
  20.    for (int k=low; k>0; k=k-1)
  21.      {
  22.        num_iterations++;
  23.        if ( (low%k == 0) && (high%k == 0) )
  24.           return k;
  25.      }
  26. }
  27.  
  28.  
  29. int main()
  30. {
  31.   int i;
  32.   int j;
  33.   int num_euclid = 0;
  34.   int num_slow   = 0;
  35.  
  36.   int my_gcd;
  37.  
  38.   // read numbers from input
  39.  
  40.   cin >> i;
  41.   cin >> j;
  42.  
  43.   // compute GCD
  44.  
  45.   my_gcd = gcd(i, j, num_euclid);
  46.  
  47.   cout << "gcd(" << i << "," << j << ") = " << my_gcd << endl;
  48.   cout << "number of iterations of Euclid's algorithm: " << num_euclid << endl;
  49.  
  50.   my_gcd = gcd_slow(i, j, num_slow);
  51.  
  52.   cout << "gcd(" << i << "," << j << ") = " << my_gcd << endl;
  53.   cout << "number of iterations of the slow algorithm: " << num_slow << endl;
  54.  
  55.   return 0;
  56. }
Success #stdin #stdout 0.02s 2728KB
comments (?)
stdin
copy 
4223453
127567
stdout
copy 
gcd(4223453,127567) = 1
number of iterations of Euclid's algorithm: 10
gcd(4223453,127567) = 1
number of iterations of the slow algorithm: 127567
https://ideone.com/QXEkF
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!