Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

An Algorithm to find a Prime Decompisition

  1. Oct 19, 2004 #1


    User Avatar

    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?

  2. jcsd
  3. Oct 19, 2004 #2


    User Avatar
    Science Advisor
    Homework Helper

    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook