1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: An Algorithm to find a Prime Decompisition
  1. Prime number algorithm (Replies: 4)

  2. Prime Number Algorithm (Replies: 3)