Fastest way to find LCM and HCF of multiple numbers?

Question

Is there any shortcut approach to find LCM and HCF of multiple numbers apart from prime factorization and hit and trial method (writing down all the multiples of respective numbers and comparing them for finding common multiple)?

Answer 1

Note that $$ \operatorname{HCF}(a, b, c) = \operatorname{HCF}(\operatorname{HCF}(a, b), c) $$ and similarily for LCM. So using an algorithm which is efficient for two numbers (say, the Euclidean algorithm for HCF, or multiplying them and dividing them by the HCF to get the LCM) will be relatively efficient for more than two numbers as well, just applied repeatedly.

---

Example: $a = 6, b = 10$ and $c = 15$. Then their HCF is $1$, and their LCM is $30$ (this is easily confirmed with prime factorisations, for instance). Following my desciption above, we get $$ \operatorname{HCF}(6, 10, 15) = \operatorname{HCF}(\operatorname{HCF}(6, 10), 15) $$ so first we find $\operatorname{HCF}(6, 10)$ with the Euclidean algorithm: $$ \operatorname{HCF}(6, 10) = \operatorname{HCF}(4, 6)\\ = \operatorname{HCF}(2, 4) = \operatorname{HCF}(0, 2) = 2 $$ which then gives $$ \operatorname{HCF}(\operatorname{HCF}(6, 10), 15) = \operatorname{HCF}(2, 15)\\ = \operatorname{HCF}(1, 2) = 1 $$ As for LCM, we get $$ \operatorname{LCM}(6, 10, 15) = \operatorname{LCM}(\operatorname{LCM}(6, 10), 15) $$ so first we find $\operatorname{LCM}(6, 10)$. We know from above that their HCF is $2$, so the LCM is $6\cdot 10\div 2 = 30$. Thus $$ \operatorname{LCM}(\operatorname{LCM}(6, 10), 15) = \operatorname{LCM}(30, 15) $$ The Euclidean algorithm gives $\operatorname{HCF}(30, 15) = 15$, so $\operatorname{LCM}(30, 15) = 30\cdot 15\div 15 = 30$.