HCF of given numbers

Question

whats the logic for calculating HCF of given numbers?

Answer 1

The usual way to calculate the highest common factor, more commonly called the greatest common divisor, is Euclid's algorithm.

If you want to calculate the HCF of more than two numbers, say i₁, i₂, i₃, ..., i_n, one algorithm is:

res = gcd(i[1], i[2])
for j = 3..n do
    res = gcd(res, i[j])
end
return res

Answer 2

Here's an implementation of Euclid's algorithm in C++:

unsigned int hcf(unsigned int a, unsigned int b) {
   if (b == 0) {
      return a;
   } else {
      return hcf(b, a % b);
   }
}