Find prime factors in C++ Please review this code.

#include &lt;iostream&gt;
#include &lt;vector&gt;

bool is_prime(int x)
{
    int flag = 1;
    for (int i = 2; i &lt;= 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&lt;int&gt;&amp; vec)
{
    int val = n;
    for (int i = 2; i &lt;= n; i++)
    {
        if (is_prime(i))
        {
            while (val % i == 0 &amp;&amp; val != 1)
            {
                vec.push_back(i);
                val = val/i;
            }
            if (val == 1)
            {
                break;
            }
        }
    }
}

int main()
{
    int n;
    std::cout &lt;&lt; "Enter number\n";
    std::cin &gt;&gt; n;
    std::vector&lt;int&gt; prime_factors;
    find_prime_factors(n, prime_factors);
    std::cout &lt;&lt; "Prime Factors of " &lt;&lt; n &lt;&lt; ":\n";
    for (int i = 0; i &lt; prime_factors.size(); i++)
    {
        std::cout &lt;&lt; prime_factors[i] &lt;&lt; " ";
    }
    std::cout &lt;&lt; "\n";
}
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:


return condition instead of if condition return true; else return false;
return early.
Use appropriate return types.
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 &lt;= 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&lt;int&gt; example = {1,2,3,4,5};
find_prime_factors(10, example); // whoops!


So instead have find_prime_factors return its result:

std::vector&lt;int&gt; find_prime_factors(int n)
{
    int val = n;
    std::vector&lt;int&gt; result;
    for (int i = 2; i &lt;= n; i++)
    {
        if (is_prime(i))
        {
            while (val % i == 0 &amp;&amp; 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 &amp;= 2\cdot 2 \cdot 105 &amp;\text{ the next factor is } 3 \\
&amp;= 2\cdot 2 \cdot 3 \cdot 35 &amp;\text{ the next factor is } 5 \\
&amp;= 2\cdot 2 \cdot 3 \cdot 5 \cdot 7 &amp;\text{ the next factor is } 7 \\
&amp;= 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&lt;int&gt; find_prime_factors(int n)
{
    int val = n;
    std::vector&lt;int&gt; result;
    for (int i = 2; i &lt;= n; i++)
    {
        while (val % i == 0 &amp;&amp; val != 1)
        {
            result.push_back(i);
            val = val/i;
        }
        if (val == 1)
        {
            break;
        }
    }
    return result;
}


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

std::vector&lt;int&gt; find_prime_factors(int n)
{
    std::vector&lt;int&gt; result;
    for (int i = 2; i &lt;= 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 &lt;typename OutputIt&gt; 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.