Method 2: Division Method (Euclid’s Algorithm) — for HCF of two numbers

Divide the larger number by the smaller; then divide the previous divisor by the remainder; keep repeating until the remainder is 0. The last non-zero divisor is the HCF. This is far faster than factorization for large or “ugly” numbers.