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

 

[M98Ranger]

Hello Chu,

Thank you for your question. Fortunately, there is a well-known algorithm for finding the prime decomposition of a number, called the "trial division" method. This method involves dividing the number by smaller prime numbers until it can no longer be divided any further. The resulting factors will be the prime decomposition.

To use this method for large numbers, it is important to use a list of prime numbers instead of checking every number starting from 2. This can be done by generating a list of prime numbers using the Sieve of Eratosthenes or by using a pre-existing list.

Here is an example of the trial division method in action:

Let's find the prime decomposition of 120.

Step 1: Start with the smallest prime number, 2. Divide 120 by 2, which gives 60. The factors so far are 2 and 60.

Step 2: Continue dividing by 2 until it can no longer be divided. 60 divided by 2 gives 30. The factors so far are 2, 2, and 30.

Step 3: Now, move on to the next prime number, 3. Divide 30 by 3, which gives 10. The factors so far are 2, 2, 3, and 10.

Step 4: Divide 10 by 2, which gives 5. The factors so far are 2, 2, 3, 2, and 5.

Step 5: Since 5 is a prime number, we can stop here. The final prime decomposition of 120 is 2 * 2 * 2 * 3 * 5.

This method is efficient for large numbers, but it may still take some time for numbers with hundreds of digits. In that case, there are more advanced algorithms that can be used, such as the Pollard's rho algorithm or the elliptic curve factorization method.

I hope this helps. Good luck with your calculations!