Archived

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

factoring

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

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