An Algorithm to find a Prime Decompisition

  • Thread starter Chu
  • Start date
  • #1
Chu
10
0
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
 

Answers and Replies

  • #2
Zurtex
Science Advisor
Homework Helper
1,120
1
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
 

Related Threads on An Algorithm to find a Prime Decompisition

  • Last Post
Replies
3
Views
4K
  • Last Post
Replies
4
Views
6K
  • Last Post
Replies
1
Views
3K
Replies
4
Views
4K
Replies
6
Views
3K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
11
Views
3K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
10
Views
2K
Top