Prime Factors

• 10-02-2007
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
• 10-02-2007
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.
• 10-02-2007
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...
• 10-02-2007
Daved
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.