Hello, I am having a problem with my program that finds the prime factorization of a number. I seem to be getting the correct prime factors, but my problem is with repeating factors. For example, if I input 3,428, the correct prime factorization is 2 x 2 x 857, but my program will only output 2 one time. Any hint on what I could try? Thanks in advance!

#include <iostream>
using namespace std;
void prime_num(int);
int main()
{

int num = 0;
cin >> num;
prime_num(num);
system ("pause");
}
 
void prime_num( int num)
{
		bool isPrime=true;
		for ( int i = 0; i <= num; i++)
		{
				for ( int j = 2; j <= num; j++)
				{
						if ( i!=j && i % j == 0 )
						{
						  isPrime=false;
						  break;
						}
				}
				if (isPrime)
				{
				 if (num % i == 0)
				  {cout << i << endl;
                                  //I thought that by dividing num by i it would loop back and divide by 2 again, but it didn't. Is there something I am missing?
				  num = num / i;
				  }
				  
				 else 
				 {i++;}
				}
				isPrime=true;
		}
}

The problem is the way you have written your outer for loop, even though you don't increment i when out output a factor the loop always increments i so you never test the same factor twice.

However if you remove the i++ from the loop you will have another problem, since the way your loops are written you end up testing 1 and since 1 is a factor of everything you end up in an infinite loop. You need to avoid testing 1.

Finally your inner loop to see if i is prime is superfluous. If i isn't prime then num % i will be non-zero because you will have already tested num for the prime factors of i. The inner is just a slow way of working out if you need to test num against i when if it fails that test itself will fail anyway. But if you insist on keeping that loop then j only needs to go up to the value of i, values greater than the current of i can not be factors of i.

This article has been dead for over six months. Start a new discussion instead.