• Advertisement

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.

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites

  • Advertisement