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

Method 3 - Euclidean algorithm with modulo operator

Basic Euclidean Algorithm to find GCD of two numbers using modulo operator