Find GCD of two numbers

Problem

Given 2 numbers, calculate the GCD of them.

Definition

GCD of two numbers is the largest number that divides both of them. A simple way to find GCD is to factorize both numbers and multiply common factors.

Examples

Example 1:

Input: a = 36, b = 60
Output: 12
Explanation:
36 = 2 x 2 x 3 x 3
60 = 2 x 2 x 3 x 5

GCD = multiplication of common factors
    = 2 x 2 x 3
    = 12

More examples:

GCD(10, 15) = 5
GCD(35, 10) = 5
GCD(31, 2) = 1

Method 1 - Naive

A simple solution is to [Find all prime factors of given number](find-all-prime-factors-of-given-number) of both numbers, then find intersection of all factors present in both numbers. Finally return product of elements in the intersection.

Method 2 - Recursive Euclidean solution with subtraction

[Subtractive Euclidean Algorithm to find GCD of two numbers](subtractive-euclidean-algorithm-to-find-gcd-of-two-numbers)

Method 3 - Euclidean algorithm with modulo operator

[Basic Euclidean Algorithm to find GCD of two numbers using modulo operator](basic-euclidean-algorithm-to-find-gcd-of-two-numbers-using-modulo-operator)