• ### Popular Now

• 11
• 9
• 10
• 9
• 11

#### Archived

This topic is now archived and is closed to further replies.

# Factoring integers

This topic is 5306 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

After lots and lots of thinking, I still cannot correctly code a program to factor integers into its prime products. My program correctly factors 100 (2,2,5,5) and 6 (2,3) and a few others. But it does not factor 16 (it says 2,2) or 4 (it says 2) and others like 81 (it says 3,9) and 32, and 40, etc. I''ve been over this many a times. Is there some pseudocode that describes the algorithm for breaking down integers into prime factors (fast and efficiently)? Thank you!

##### Share on other sites
The Rho algorithm works nicely.

http://www.csh.rit.edu/~pat/math/quickies/rho/

There will be plenty of other explanations of it if you google

##### Share on other sites
Post your code and I''ll tell you what''s wrong with it.

##### Share on other sites
I second alvaro''s approach. Show us your work, and perhaps we can give you some clues as to how to fix it.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

##### Share on other sites

A. Find lowest factor of int starting at 2. If none, END, otherwise continue.
B. If factor is prime, print/save it and goto: D, otherwise continue.
C: Find next lowest factor of int. goto: B
D: Divide your int by the prime factor, goto: A

Something like that would be pretty simple.

##### Share on other sites
Factoring is NP-complete, which is relevant to you in that one can be fairly certain that it has to be done in exponential time or above. What I do is square root the number to get the maximum value of any prime factor. Then take all the primes under this square root, find the first one that divides it exactly and then divide your number by this and repeat on your new number, until you get 1 as your new number.

##### Share on other sites
quote:
Original post by furby100
Factoring is NP-complete

Where did you hear that? Last time I checked, it was unknown.

http://www.wikipedia.org/wiki/Integer_factorization

##### Share on other sites
quote:
Original post by furby100
Factoring is NP-complete, which is relevant to you in that one can be fairly certain that it has to be done in exponential time or above. What I do is square root the number to get the maximum value of any prime factor. Then take all the primes under this square root, find the first one that divides it exactly and then divide your number by this and repeat on your new number, until you get 1 as your new number.

I''m skeptical, too.

Some Indian guys discovered a algorithm for factoring integers efficiently (in polynomial time). Unfortunately, I can''t find the article right now (am at school). I have it at home and will post it soon. If factoring was NP-complete, wouldn''t they get the $1 million for proving P=NP? #### Share this post ##### Link to post ##### Share on other sites quote: Original post by GaulerTheGoat Some Indian guys discovered a algorithm for factoring integers efficiently (in polynomial time). Nope. What was recently proved is that primality testing can be done in polynomial time. quote: If factoring was NP-complete, wouldn''t they get the$1 million for proving P=NP?

If factoring were NP-complete and they have an algorithm that factors in polynomial time, yes. The former is not known and the latter is false.

Please, stop posting if you don''t know what you are talking about.