Greatest Common Divisor

Calendar Clock iconCalendar Clock icon

number-theory

Table of contents

# Usage

Determine the geatest common divisor of 2 numbers.

# Algorithm

Euclidean algorithm

Given 2 numbers, let the smaller x and the other y.

Repeat the following until y is 0.

  • r = x % y
  • x = y
  • y = x

The x is the GCD.

# Time Complexity

Let the count of modulo arithmetic bb,

O(log⁡b)O(\log b)

# Code

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;
Int gcd(Int x, Int y) {
  if (x > y) swap(x, y);
  
  Int r;
  while (y > 0) {
    r = x % y;
    x = y;
    y = r;
  }
  return x;
}

Shun

Github Circle icon

Remote freelancer. A web and mobile application enginner.
Traveling around the world based on East Asia.
I'm looking forward to your job offers from all over the world!

Offer jobs or contact me!

Comments