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

## Recommended Posts

how can i get the factors of a number?

##### Share on other sites
Take the number and start dividing by every number from 2 to the square root of the original number.

##### Share on other sites
Don''t forget 1 and the number itself.

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

##### Share on other sites
Don''t you mean .999999... and the number itself?

*ducks and runs*

##### Share on other sites
is there a faster method perhaps?

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

##### 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 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 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 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 on other sites
Aprosenf: Hm?
>> 216
2 2 2 3 3 3

Looks like it works to me. What number would break it?

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

• ### Forum Statistics

• Total Topics
628728
• Total Posts
2984418

• 25
• 11
• 10
• 16
• 14