#include <algorithm>
#include <chrono>
#include <iostream>

using namespace std;

int gcdEuclideanIterative(int a, int b) {
  while (b != 0) {
    int temp = b;
    b = a % b;
    a = temp;
  }
  return a;
}

int gcdEuclideanRecursive(int a, int b) {
  if (b == 0) {
    return a;
  }
  return gcdEuclideanRecursive(b, a % b);
}

int gcdCommonFactors(int a, int b) {
  int gcd = 1;
  for (int i = 1; i <= min(a, b); ++i) {
    if (a % i == 0 && b % i == 0) {
      gcd = i;
    }
  }
  return gcd;
}

bool isPrime(int n) {
  if (n <= 1)
    return false;
  if (n <= 3)
    return true;
  if (n % 2 == 0 || n % 3 == 0)
    return false;
  for (int i = 5; i * i <= n; i += 6) {
    if (n % i == 0 || n % (i + 2) == 0)
      return false;
  }
  return true;
}

int gcdMiddleSchool(int a, int b) {
  int gcd = 1;

  for (int i = 2; i <= min(a, b); ++i) {
    if (isPrime(i)) {
      while (a % i == 0 && b % i == 0) {
        gcd *= i;
        a /= i;
        b /= i;
      }
    }
  }

  return gcd;
}

int main() {
  int a = 48, b = 18;

  auto start = chrono::high_resolution_clock::now();
  int gcdIterative = gcdEuclideanIterative(a, b);
  auto end = chrono::high_resolution_clock::now();
  chrono::duration<double> timeIterative = end - start;

  start = chrono::high_resolution_clock::now();
  int gcdRecursive = gcdEuclideanRecursive(a, b);
  end = chrono::high_resolution_clock::now();
  chrono::duration<double> timeRecursive = end - start;

  start = chrono::high_resolution_clock::now();
  int gcdCommon = gcdCommonFactors(a, b);
  end = chrono::high_resolution_clock::now();
  chrono::duration<double> timeCommon = end - start;

  start = chrono::high_resolution_clock::now();
  int gcdMiddle = gcdMiddleSchool(a, b);
  end = chrono::high_resolution_clock::now();
  chrono::duration<double> timeMiddle = end - start;

  cout << "GCD of " << a << " and " << b << ":\n";
  cout << "Euclidean Iterative: " << gcdIterative
       << ", Time: " << timeIterative.count() << " seconds\n";
  cout << "Euclidean Recursive: " << gcdRecursive
       << ", Time: " << timeRecursive.count() << " seconds\n";
  cout << "Common Factors: " << gcdCommon << ", Time: " << timeCommon.count()
       << " seconds\n";
  cout << "Middle School: " << gcdMiddle << ", Time: " << timeMiddle.count()
       << " seconds\n";

  return 0;
}