Factoring integers
Author
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!
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
http://www.csh.rit.edu/~pat/math/quickies/rho/
There will be plenty of other explanations of it if you google
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.
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
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.
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.
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
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?
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
