Jump to content
• Advertisement

#### Archived

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

# Factoring integers

This topic is 5488 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

##### 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

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

#### Share this post

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

##### 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

##### 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

##### 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

##### Share on other sites
lol can anyone crack 1024 bits RSA keys on his PC here ?

#### Share this post

##### Share on other sites

• Advertisement
• Advertisement

• ### Popular Contributors

1. 1
Rutin
44
2. 2
3. 3
4. 4
5. 5
• Advertisement

• 11
• 9
• 12
• 10
• 13
• ### Forum Statistics

• Total Topics
632983
• Total Posts
3009708
• ### Who's Online (See full list)

There are no registered users currently online

×

## Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!