# Greatest Common Divisor

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 $b$,

$O(\log b)$

# # Code

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;
}


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!