To find : divide, take remainder, repeat. , , . HCF is the last non-zero remainder: . Nothing beats it for speed on large numbers.
Back to The World of Algorithms
Class 9 · Ganita Manjari · Unit 11: The World of Algorithms
The Euclidean Algorithm — 2300 Years Old and Still Best
Lesson 2 of 3