C++ : Program that gives u the prime factors

[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 I am 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;
}

 

[hamster143]

Try to do this slightly differently:

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

 

[aleee]

any certain direction i should go in?

 

[hamster143]

I don't understand your question.

 

[aleee]

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

 

[hamster143]

Do you see the code in my post?

 

[aleee]

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

 

[Mark44]

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.