Jump to content
  • Advertisement

Archived

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

vaneger

factoring

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

Advertisement
Take the number and start dividing by every number from 2 to the square root of the original number.

Share this post


Link to post
Share on other sites
Don''t forget 1 and the number itself.


"Sneftel is correct, if rather vulgar." --Flarelocke

Share this post


Link to post
Share on other sites
Not really. That's the basis behind many kinds of cryptography: factoring numbers is hard.

edit: technically, you can pull out the prime factors as you find them and regenerated the full factors from the combinations of powers of prime factors, but if the number itself is prime, then the problem degenerates checking the prime numbers from 2 to sqrt of the number.

[edited by - SiCrane on April 3, 2004 6:59:38 PM]

Share this post


Link to post
Share on other sites

#include <cmath>

int main()
{
int Num = 676;
int Root = sqrt(Num);
int Divisor = 2;

while(Divisor <= Root)
{
if(Num % Divisor == 0)
{
Num /= Divisor;
printf("%d\n", Divisor);

Divisor = 1;
}

++Divisor;
}

if(Num != 1)
printf("%d\n", Num);

return 0;
}

This will print the prime factorization of a number, which isn''t quite what you asked for, but which may also prove useful.

Later,
ZE.

//email me.//zealouselixir software.//msdn.//n00biez.//
miscellaneous links

Share this post


Link to post
Share on other sites
quote:
Original post by ZealousElixir
This will print the prime factorization of a number, which isn't quite what you asked for, but which may also prove useful.



No, it won't. If the number is prime, it will print out nothing. Or if the number is composed as the product of two prime numbers then only the first prime will be listed. (You're hitting a boundary condition badly in your loop.)

edit: never mind, I'm an idiot

[edited by - SiCrane on April 3, 2004 7:02:56 PM]

Share this post


Link to post
Share on other sites
actually i goofed i dont need numbers that multiply to get a producti need numbers that add to get a number how can i find that? such as 2 + 5 = 7 or 3 + 4 = 7 etc

Share this post


Link to post
Share on other sites
Not quite. That doesn''t work if a number contains the square or higher power of a prime. Here''s a function that will return a vector of the prime factorization of a number:

#include <vector>

using namespace std;

struct PrimeFactor
{
PrimeFactor() {}
PrimeFactor(int pr, int po) { prime = pr; power = po; }

int prime;
int power;
};

void PrimeFactorization(int num, vector<PrimeFactor> & result)
{
int factor, power;

for(factor = 2; factor * factor <= num; factor++) // You can be more efficient by checking 2 and then doing for(factor = 3; factor * factor <= num; factor += 2)

{
if(num % factor == 0)
{
power = 1;

do
{
num /= factor;

power++;
} while(num % factor == 0);

result.push_back(PrimeFactor(factor, power));
}
}
}

Share this post


Link to post
Share on other sites

  • Advertisement
×

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!