11
\$\begingroup\$

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";
}
\$\endgroup\$
  • \$\begingroup\$ In your loop checking for prime you iterate to x/2 which does not represent the square root as you intend. Technically the loop should still cover the desired range. i * i <= x would be more optimal. Or while(i * i <= x) \$\endgroup\$ – AGirlHasNoName Apr 11 '18 at 16:38
25
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Unfortunately gcc and clang are dumb and don't take advantage of division producing the modulo for free and vice versa, so there are actually two idiv instructions in the inner loop unless you mangle the source code to hand-hold the compilers into not sucking. reported gcc.gnu.org/bugzilla/show_bug.cgi?id=85366 and bugs.llvm.org/show_bug.cgi?id=37101. BTW, you mentioned not checking even numbers > 2 for primality, but worth mentioning it again for the trial-division loop in find_prime_factors. Current compilers also fail to optimize that for you. \$\endgroup\$ – Peter Cordes Apr 12 '18 at 7:23
  • \$\begingroup\$ @PeterCordes yeah, compilers are somewhat dumb. I'll add a std::div remark. \$\endgroup\$ – Zeta Apr 12 '18 at 7:25
  • \$\begingroup\$ IDIV is x86 specific, though. ARM's Cortex-M3 for example don't store the remainder, and std::div can lead to a small overhead there. I'll check GCC's std::div implementation later today. \$\endgroup\$ – Zeta Apr 12 '18 at 7:31
  • \$\begingroup\$ x86 isn't the only ISA that produces div and mod in one instruction. (e.g. MIPS uses the lo/hi regs for output from division). Even on ARM, if you need both you'd want to divide, then multiply and subtract instead of running a separate modulo instruction. Compilers are fine at CSEing x / y and x % y when they're in the same block; so normally std::div is pure loss because it doesn't typically inline, and the x86-64 SysV calling convention requires it to pack both 32-bit members into RAX. But it's a win here if you don't want to make the source ugly: godbolt.org/g/zET9YY \$\endgroup\$ – Peter Cordes Apr 12 '18 at 7:38
  • 1
    \$\begingroup\$ @MatthieuM. Full ACK. I think I'll edit my answer later, currently mobile. \$\endgroup\$ – Zeta Apr 12 '18 at 15:17
4
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ It's probably worth it to sqrt once instead of squaring every time time inside the loop, at least on modern CPUs that have fast floating-point sqrt hardware and fast conversion from int to double. Or maybe not because sqrt will use the same divider hardware as trial-division, so out-of-order execution can't let the first few iterations get started while waiting for p <= max_p condition to evaluate. And if you're lucky, a smart compiler will strength-reduce p*p to psquared += p. \$\endgroup\$ – Peter Cordes Apr 12 '18 at 7:44
  • \$\begingroup\$ Peter the max_p isnt constant since n is a moving/shrinking target. Computationally sqrt is more expensive than squaring. However having said that there's optimization possible to reduce the need for frequent squaring. \$\endgroup\$ – Stephen Quan Apr 12 '18 at 11:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.