An Algorithm to find a Prime Decompisition

[Chu]

Hello all. I know there is a stupidly easy algorithm to find the prime decompision of a number (i.e. 2*2*2*3*5 is the p.d. of 120) but I can't for the life of me remember it. I need to do this operation on incredibly large numbers (~500 digits) so the naieve way of just starting at 2 and proceding through the primes *PROBABLY* doesn't work (if it does -- please tell me!) but I know there is a less naieve but still simplistic algorithm. Anyone out there know it?

-Chu

[Zurtex]

I'm sorry to say but there isn't a quick way to do it. Factorising large numbers quickly is one of the holy grails of number theory.

There are however obvious things you can do to make it a little quicker. Where m is your number and p_n is a prime you are dividing by there are a couple of things to remember when making an algorithm. You only need to go up to the square root of m by default. Your general line is does m/p_n = int(m/p_n)? If yes try it again and if no move on to the next prime. Also if yes you can set the maximum number you need to check up to as squareroot(m)/p_n.

There may be a faster way I am not aware of but it still won't be able to deal with very big numbers quickly. For example the matlab factor command only allows a limit of numbers as big as 2^32