Prime factorization in C++

Question

I wanted to know how I can print the decomposition of a number into factors in a single line, because in my case when the divisor changes, it prints a new line, i.e:

392 = 2^3 * 7^2

And not:

392 = 2^3
392 = 7^2

#include <iostream>

int main() {
  int n, dig, num, i, val;

  do {
    std::cout << "Enter a number greater than one: ";
    std::cin >> n;
  } while (n <= 1);

  i = 2;
  val = 0;
  num = n;

  do {
    dig = num % i;

    if (dig == 0) {
      do {
        num = num / i;
        dig = num % i;
        val = val + 1;
      } while (dig == 0);

      std::cout << n << " = " << i << "^" << val << std::endl;
    }

    val = 0;
    i = i + 1;
  } while (num != 1);

  return 0;
}

Answer 1

You're doing the stuff a bit too complicated at some points on the one hand while you missed some (minor?) issues on the other hand...

A very simple approach could instead look like this:

std::cout << n;         // output this only once, thus *before* entering the loop
auto separator = " = "; // this will be the initial separator

// now iterating over all numbers that *might* be factors
for(int i = 2; i*i <= n; ++i)
{
    unsigned int count = 0;
    while(n % i == 0)
    {
        n /= i;
        ++count;
    }
    if(count != 0) // you don't want to output `i^0`, do you?
    {
        std::cout << separator << i << '^' << count;
        // now that we wound a factor we need to adjust the separator
        // so that we do not print out " = " for next factor, too:
        separator = " * ";
    }
}

// due to testing `i*i <= n` we NOW need this additional test as
// the remaining n might be prime:
if(n != 1)
{
    std::cout << separator << n << "^1";
}
// finally close the line and flush
std::cout << std::endl;

The separator variable serves for printing = the first time a value is found and * otherwise. Just exchanging the pointer on need is a much simpler – and much more efficient – approach than branching within the loop (std::cout << (alreadyFound ? " * " : " = ")).

Further optimisations comprise on the one hand the outer loop; testing for i*i <= n avoids testing values of i that cannot be a factor of the remaining n anyway – however, as shown above, we do not find n itself if that one's getting a prime number, so we need to handle that separately. If n gets 1 in the meanwhile – never mind, i*i will still remain larger, so that's actually covered.

The second optimisation, on the other hand:

if(condition)
{
    do { doSomething(); } while(condition); // exactly the same one!
}

is fully equivalent to

while(condition) { doSomething(); }

The first time the loop condition is tested cover's the original if – if the condition isn't met already now the loop simply won't be entered either...

Note that this is entirely untested code – if you find a bug, please fix yourself.

Just as a side note: for(int i = 2; i*i <= n; ++i) is, apart from the test for i*i < n (the modified number), the most primitive variant you might chose. You could still optimise, but this will result in more complex code - you have the same choices for as when testing for prime numbers (you'll find references here on SO as well). Least complex of these optimisations (with least performance boost): Calculate 2 separately before the loop and then have for(int i = 3; i*i <= n; i += 2)...