Page 1 of 1

Fast prime factorization method?

Posted: Fri Oct 26, 2007 11:23 am
by fullofquestions
To answer the lcm and gcd questions you need to factor a number into its prime factorization. I've seen many examples of fairly large numbers that are factored matter of fact. I understand that you can use the basic divisibility rules to get started and continue to end up with

some large number = 2^a * 3^b * 5^c * 7^d * 11^e (where a to e are integers >= 0)

I'm just curious if there is a trick to this. I understand that most times, you will not have an easy prime factorization and need to resort to the eucledian algorithm.