Euclidean algorithm

Wiki

In mathematics, the Euclidean algorithm or Euclid’s algorithm, is an efficient method for computing the greatest common divisor (GCD) of two numbers, the largest number that divides both of them without leaving a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in Euclid’s Elements (c. 300 BC). It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations. wiki

Implementation

Recursive

1
2
3
int gcd(int a, int b) {
return b? gcd(b, a%b):a;
}

Iterative

1
2
3
4
5
6
7
8
9
10
int gdc(int a, int b)
{
if(!b) return a;
while(b){
int t = b;
b = a%b;
a = b;
}
return a;
}

Always welcome new ideas and practical tricks, just leave them in the comments!