Find prime factors in C++

Question

Please review this code.

#include <iostream>
#include <vector>

bool is_prime(int x)
{
    int flag = 1;
    for (int i = 2; i <= x/2; i++)
    {
        if (x % i == 0)
        {
            flag = 0;
            break;
        }
    }
    if (flag == 1)
    {
        return true;
    }
    else if (flag == 0)
    {
        return true;
    }
}

void find_prime_factors(int n, std::vector<int>& vec)
{
    int val = n;
    for (int i = 2; i <= n; i++)
    {
        if (is_prime(i))
        {
            while (val % i == 0 && val != 1)
            {
                vec.push_back(i);
                val = val/i;
            }
            if (val == 1)
            {
                break;
            }
        }
    }
}

int main()
{
    int n;
    std::cout << "Enter number\n";
    std::cin >> n;
    std::vector<int> prime_factors;
    find_prime_factors(n, prime_factors);
    std::cout << "Prime Factors of " << n << ":\n";
    for (int i = 0; i < prime_factors.size(); i++)
    {
        std::cout << prime_factors[i] << " ";
    }
    std::cout << "\n";
}

Answer 1

Your program has a bug. is_prime returns true in all possible return situations. You don't notice that because your prime factors already use a nice property of prime factors which we inspect later. Here's a short list of improvements first:

1. return condition instead of if condition return true; else return false;
2. return early.
3. Use appropriate return types.
4. Modify algorithms.

Now let's focus on the bug first.

is_prime

First, the obvious: both return statements only return true. However, there are some improvements we can apply. First, if two conditions are exclusive and cover the whole range of possible conditions use if/else without a second if:

if (flag == 1)
{
    return true;
}
else // no if here!
{
    return true;
}

Note that this still contains your bug above. This brings us to our next improvement: instead of

if (condition) {
    return true;
} else {
    return false;
}

just return condition:

return (flag == 1);

Note that this completely removes the bug already. But we can go further. flag itself introduces a source for possible bugs. We could accidentally use flag = 3 (which can be mediated by bool flag) or forget to set flag (which can be checked by statical analysis).

But we don't need flag. Either we break the loop (and therefore flag = 0) and we return false, or we won't and return true. This is a perfect opportunity to use early returns:

bool is_prime(int x)
{
    for (int i = 2; i <= x/2; i++)
    {
        if (x % i == 0)
        {
            return false;
        }
    }
    return true;
}

There are two optimizations that are left for exercise. First, we don't need to check every i, but only every second. If x % 2 != 0, then x % i != 0 for all even i. Also, for any pair of factors \$ab=x\$ holds \$a\le b\$ and therefore \$a\le \sqrt{x}\$. Both optimizations are left as an exercise.

find_prime_factors

We now have a look at 3., "use appropriate return types". Your function's result is a vector. Nothing in its interface prevents a user to supply an already filled vector, e.g.:

std::vector<int> example = {1,2,3,4,5};
find_prime_factors(10, example); // whoops!

So instead have find_prime_factors return its result:

std::vector<int> find_prime_factors(int n)
{
    int val = n;
    std::vector<int> result;
    for (int i = 2; i <= n; i++)
    {
        if (is_prime(i))
        {
            while (val % i == 0 && val != 1)
            {
                result.push_back(i);
                val = val/i;
            }
            if (val == 1)
            {
                break;
            }
        }
    }
    return result;
}

Next, we'll focus on the algorithm. As you noticed, find_prime_factors worked, even though is_prime is broken. Why?

When you divide a number by its smallest prime factor, the next number that will divide the new number must be a prime factor. Let's try it by hand:

$$ \begin{align} 420 &= 2\cdot 2 \cdot 105 &\text{ the next factor is } 3 \\ &= 2\cdot 2 \cdot 3 \cdot 35 &\text{ the next factor is } 5 \\ &= 2\cdot 2 \cdot 3 \cdot 5 \cdot 7 &\text{ the next factor is } 7 \\ &= 2\cdot 2 \cdot 3 \cdot 5 \cdot 7 \cdot 1 \end{align} $$ We don't need the is_prime check at all:

std::vector<int> find_prime_factors(int n)
{
    int val = n;
    std::vector<int> result;
    for (int i = 2; i <= n; i++)
    {
        while (val % i == 0 && val != 1)
        {
            result.push_back(i);
            val = val/i;
        }
        if (val == 1)
        {
            break;
        }
    }
    return result;
}

Also, we can stop as soon as i > val, because at that point val == 1. In fact, we can get rid of val altogether and just modify n:

std::vector<int> find_prime_factors(int n)
{
    std::vector<int> result;
    for (int i = 2; i <= n; i++)
    {
        while (n % i == 0)
        {
            result.push_back(i);
            n /= i;
        }
    }
    return result;
}

At some point n == i and n /= i will yield n == 1, so we don't have to worry about an infinite loop. This algorithm is also known as trial division. Note that we can also apply the optimization for even numbers here (left as another exercise).

There are other optimizations that one can apply:

• reserve memory beforehand (a number \$N\$ can have at most \$\log_2 N\$ factors, so std::vector::reserve can be used)
• use methods that yields both quotient and divisor at the same time (very platform specific).

For a fun exercise, you can rewrite it with iterators in mind:

template <typename OutputIt> OutputIt(int n, OutputIt out) {
    // exercise
}

Note that this is somewhat an overkill, since n will contain at most 64 prime factors if your int uses 64 bits.

Bottom line

Check all your functions. is_prime contained a nasty bug. Other than that your code is nicely structured, doesn't use using namespace and was easy to read.

Answer 2

When I wrote my answer I thought it was different to the accepted answer. After rereading the accepted answer, I realised the algorithm presented in both are actually the same. I decided to leave my answer here since the explanation and presentation is different.

This answer focuses on a short simple solution to the problem.

#include <iostream>

int main() 
{
  int n;
  std::cout << "Enter number\n";
  std::cin >> n;
  for (int p = 2; n > 1 && p <= n; p++)
  {
    while (n % p == 0)
    {
      std::cout << p << " ";
      n /= p;
    }
  }
  std::cout << n << "\n";
}

In the solution, we see no mention of primes whatsoever, it appears we're testing every value of p between 2..n, and that's correct. We are. However, the result is always a list of primes? Why?

When the program begins, and you enter 420, it tries "2"...

n    p    output       n'    p'   description
420  2    2            210   2    2 goes into 420
210  2    2 2          105   2    2 goes into 210
105  2    2 2          105   3    2 doesn't go into 105 move to next 'prime'
105  3    2 2 3        35    3    3 goes into 105
35   3    2 2 3        35    4    3 doesn't go into 35 move to next 'prime'
35   4    2 2 3        35    5    4 doesn't go into 35 move to next 'prime'
35   5    2 2 3 5      7     5    5 goes into 35
7    5    2 2 3 5      7     6    5 doesn't go into 7 move to next 'prime'
7    6    2 2 3 5      7     7    6 doesn't go into 7 move to next 'prime'
7    7    2 2 3 5 7    1     7    7 goes into 7, and we terminate loop

So, we are in fact trying every number from 2..7, but, the reason why 4 and 6 don't get a hit, is because we had already removed 2 and 3 as factors earlier. In general terms, all non prime versions of p never get a hit because we already removed the related prime factors previously.

I put std::cout << n << "\n" at the end to show the residual value of n. Typically this will be just 1. However, this is useful for handling edge conditions when the user enters 0, 1 or a negative number. We simply return the user's input back to them, rather than showing them nothing.

bruglesco suggested changing the terminating condition to p*p <= n, i.e.

  for (int p = 2; n > 1 && p*p <= n; p++)

Whilst this change, is very simple, it optimizes the algorithm dramatically meaning for an input like 97 we only test from 2..9 to realize that there's no point in checking any further. This makes the last line I added more pertinent, as it's no longer for edge condition, but, displays the last prime.