Problem Solving

For those problems which require calculation of GCD..one may use this eucliedean algorithm which is more efficient than prime factorization.

A much more efficient method is the Euclidean algorithm, which uses the division algorithm in combination with the observation that the gcd of two numbers also divides their difference: divide 84 by 18 to get a quotient of 4 and a remainder of 12. Then divide 18 by 12 to get a quotient of 1 and a remainder of 6. Then divide 12 by 6 to get a remainder of 0, which means that 6 is the gcd.

I tried timing to see if its true.

problem GCD for 92 and 20.
Prime factorization - 40s.
Euclidean - 18s

not only does prime factorization take long it may confuse sometimes during overlap..

Hope this helps cheers..

Great tip.

We all know about it but never use it.