Prime Factors

I have a program that will find prime factors of any input number

Code:

#include <iostream>

using namespace std;

int main()
{
	int n;

	cout << "Enter the number to factor:" << endl;
	cin >> n;

	int k=2;

	cout << "The prime factors of " << n << " are: " << endl;

	while (n > k*k)
	{
		if ((n%k)==0)
		{
			n=(n/k);

			cout << k << " ";

		}

		else
		{k=k+1;
		}
	}
	cout << n << " ";
}

Now, say I put in 567 as the number to factor, the output would be 3 3 3 3 7

However, if I want to switch that output to the format 3^4 7, I'm not really sure how to go about doing that.

Any help I can get would be great

Thanks

You could keep track of how many times a value k divides evenly. When it no longer divides evenly, output that value and if the count is higher than 1 output ^ and the count.

Originally Posted by Daved

You could keep track of how many times a value k divides evenly. When it no longer divides evenly, output that value and if the count is higher than 1 output ^ and the count.

I'm not sure how to keep track of something like that though, however, that is the same idea I had.

Wait, I could go n/k= first

And then output would be cout << k << " ^ " << "first"

I'll have to work with that a bit

Edit: but it's not n/k, it's how many times that process is repeated...

But you are doing them in order, so that if you find a factor k then you know it is greater or equal to the previous factor. If it is equal, then bump up the count, if not, reset the count. Only output k (and the count) when k is incremented and the count is not zero.

To see it more clearly, follow your current code through an example. Write down each step as it happens (make it a small example, like 12). Notice where you are in the code when you stop finding a particular factor. See if that helps you figure out where and how to count.