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.

Quote:

---

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.