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..
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..
