Archived

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

vaneger

factoring

Recommended Posts

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
quote:
Original post by vaneger
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


Assuming that you are dealing with integers: start with the number, subtract one. The result and 1 is one set.

Then subtract 2, the result and 2 is another set. And so on and so forth.

BTW.

I dont't think the OP asked for prime factors anyways.




[edited by - yspotua on April 3, 2004 8:52:19 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by vaneger
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


There are an infinite number solutions to that problem, you need to add some constraints.


You have to remember that you''re unique, just like everybody else.

Share this post


Link to post
Share on other sites
no there are 8 solutions to that problem i believe
0+7 1+6 2+5 3+4 7+0 6+1 5+2 4+3 or only 4 if order is limited.

Share this post


Link to post
Share on other sites
No, he was right to say there are infinite answers. For example, 100 + (-93) = 7. Now, if you add some constraints like he said...

Share this post


Link to post
Share on other sites
whole positive numbers less than or equal to the given number
the number of additive pairs is equal to (n+1)/2 with the above example of 7 the number of pairs is 4 (07,16,25,34) not counting reverses. i currently have this code

struct pr
{
int first;
int second;
};

vector<pr> pairs;

void set_pairs(int n)
{
int q = (n+1) / 2;
pairs.resize(q)
for(int i = 0; i < q;i++)
{
pairs[i].first = n - i;
pairs[i].second = n - (n-i);
}
}

but im not sure if set_pairs can be made faster or not.

Share this post


Link to post
Share on other sites