# C++ : Program that gives u the prime factors!

1. May 20, 2010

### aleee

i need help making a program that only displays the prime factors
ex: 100 = 2*2*5*5

i got the program to display all the factors but after that im lost.

here is the code so far
oh its in C++

#include <iostream>

using namespace std;

int main()
{
cout << "Enter a number: ";
int num;
cin >> num;
int i,k = 0;

for (int i=2; i <= num; i++)
{
if( num % i == 0)
{
if(num % i == 0)
{
k = num / i;
}
cout << i << " " << k << endl;
}
}
return 0;
}

2. May 20, 2010

### hamster143

Try to do this slightly differently:

Code (Text):

#include <iostream>

using namespace std;

int main()
{
cout << "Enter a number: ";
int num;
cin >> num;

for (int i=2; i <= num; i++)
{
while(num % i == 0)
{
num /= i;
cout << i << " ";
}
}
cout << endl;
return 0;
}

Last edited: May 21, 2010
3. May 20, 2010

### aleee

any certain direction i should go in?

4. May 20, 2010

### hamster143

5. May 20, 2010

### aleee

im not sure on how to go about changing it. any advice?

6. May 21, 2010

### hamster143

Do you see the code in my post?

7. May 21, 2010

### aleee

oh sorry my mistake. i ended up doing a while loop then a for loop inside, but thank you for the help

8. May 21, 2010

### Staff: Mentor

Something to keep in mind is that you don't have to check all of the integers from 2 to num. It is sufficient to go up to sqrt(num) - or the largest integer greater than or equal to sqrt(num). The idea is that if num has a factor smaller than sqrt(num), then there will be one larger than sqrt(num) as well.

For example, suppose num is 85. All you need to do is check the integers from 2 though 9.

Check 2 - not a divisor.
Check 3 - not a divisor.
Check 4 - not a divisor.
Check 5 - is a divisor. (The other divisor is 17.)
Check 6 - not a divisor.
Check 7 - not a divisor.
Check 8 - not a divisor.
Check 9 - not a divisor.

FYI, you don't actually need to check 4, 6, 8, 10, etc. If 2 is not a divisor, then no other even integer will be a divisor. The same is true for 6, 9, 12, etc. If 3 isn't a divisor, then neither will any other multiple 3 be a divisor. There are lots of ways to make the program more efficient, but they add complexity to the code.