Public Group

#### Archived

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

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

## 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));		}	}}

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5

• 14
• 30
• 13
• 11
• 11
• ### Forum Statistics

• Total Topics
631782
• Total Posts
3002324
×