Fast prime factorization method?

Forum for the GRE subject test in mathematics.
Post Reply
fullofquestions
Posts: 18
Joined: Sun Oct 07, 2007 1:49 pm

Fast prime factorization method?

Post by fullofquestions » Fri Oct 26, 2007 11:23 am

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.



Post Reply