Check if n-th root of product of numbers is a whole number C++ I've got an assignment which sounds like this:


  Given a number \$m\$ and \$n\$ other numbers, say if the \$m\$-th root of the product of those numbers is a whole number (print 1) or not (print 0). If yes, also print, in sorted order, the result of the \$m\$-th root, decomposed in prime factors.


This is how the expression would look:

$$\sqrt[m]{x_1 x_2 x_3 \dots x_n}$$

My idea was this: for the result to be a whole number, if we were to decompose all of the numbers, then make the product of all of them, every power of every base has to be divisible with \$m\$.

This is what I came up with:

#include &lt;iostream&gt;
#include &lt;algorithm&gt;
#include &lt;vector&gt;
using namespace std;

using Prime_factorization = vector &lt; pair&lt;int, int&gt; &gt;;

void add_base_and_power(Prime_factorization&amp; prime_factorization, int    base, int power)
{
    // Check if we've already got the base we're trying to add
    auto it = find_if(prime_factorization.begin(), prime_factorization.end(), [&amp;](pair &lt;int, int&gt; p) { return p.first == base; } );

    if (it != prime_factorization.end()) // If yes, add the power to the existing base
        it-&gt;second += power;
    else
        prime_factorization.push_back(make_pair(base, power)); // Else, create a new base
}

void check_if_is_factor(Prime_factorization&amp; prime_factorization, int &amp;number, int divisor)
{
    if (number % divisor == 0) { // If the divisor is a base, we divide until it no longer can

        int power { 0 };
        while (number % divisor == 0) {
            number /= divisor;
            ++power;
        }

        // Add base and power to factorization
        add_base_and_power(prime_factorization, divisor, power);
    }
}

void decompose(Prime_factorization&amp; prime_factorization, int number)
{
    check_if_is_factor(prime_factorization, number, 2); // Check if it divides by 2 so after that we can only check for uneven bases


    for (int div { 3 }; div * div &lt;= number &amp;&amp; number &gt; 1; div += 2)
        check_if_is_factor(prime_factorization, number, div);

    // If number is bigger than 1 it means we got out of the previous for loop with the first condition, so the number must be prime
    if (number &gt; 1)
        add_base_and_power(prime_factorization, number, 1);
}

int main() {

    // Get m-th root
    int m;
    cin &gt;&gt; m;

    // Get number of terms
    int n;
    cin &gt;&gt; n;

    // Take n numbers and decompose each of them
    Prime_factorization prime_factorization;
    for (int i { 1 }; i &lt;= n; ++i) {

        int x;
        cin &gt;&gt; x;

        decompose(prime_factorization, x);
    }

    // After decomposing all of the numbers, we check to see if each power can be divided by m(the root)
    bool okay { true };
    for (auto&amp; i : prime_factorization)
        if (i.second % m != 0) {
            okay = false;
            break;
        }

    // We must print the base-power combinations in sorted order
    sort(prime_factorization.begin(), prime_factorization.end(), [](pair&lt;int, int&gt; p1, pair&lt;int, int&gt; p2) { return p1.first &lt; p2.first; });

    if (okay) {
        cout &lt;&lt; 1 &lt;&lt; '\n';

        for (auto&amp; i : prime_factorization)
            cout &lt;&lt; i.first &lt;&lt; ' ' &lt;&lt; (i.second / m) &lt;&lt; '\n';
    } else
        cout &lt;&lt; 0;
}


How could I improve my code? Is there any better algorithm you might've thought of?
The basic approach looks sensible, but I do have a few suggestions for improvements.


using namespace std;



Bad idea. It may be a nuisance having to prepend std:: everywhere, but it's a short name in order to reduce the nuisance, and the things which could go wrong are quite bad.




void add_base_and_power(Prime_factorization&amp; prime_factorization, int    base, int power)



What happened to the whitespace in int    base? A single space suffices.

What do the names communicate and fail to communicate? The name prime_factorization communicates nothing: the type already says that. What purpose does this particular prime factorisation serve? The name base doesn't really fit the context IMO: you're not accumulating to a Base_power_pairs. add_prime_power(Prime_factorization accumulator, int prime, int power) would make it crystal clear what the function does.




void check_if_is_factor(Prime_factorization&amp; prime_factorization, int &amp;number, int divisor)



Again, names.


    if (number % divisor == 0) { // If the divisor is a base, we divide until it no longer can



This isn't wrong, but I wonder whether you made a conscious choice between this approach and

    int power { 0 };
    while (number % divisor == 0) {
        number /= divisor;
        ++power;
    }

    if (power &gt; 0)
    {
        // Add base and power to factorization
        add_base_and_power(prime_factorization, divisor, power);
    }


I find the latter more aesthetically pleasing. It doesn't do a test which it knows will succeed.

NB this point is purely a subjective point about style - I'm not trying to microoptimise, and microoptimisations should be done with good benchmarks. 




void decompose(Prime_factorization&amp; prime_factorization, int number)



What is being decomposed here? My instinct would be that the first argument is the most relevant to interpreting the function name, but that doesn't make sense in this case.


    for (int div { 3 }; div * div &lt;= number &amp;&amp; number &gt; 1; div += 2)



I've seen you use this int name { val } a few times, and (not being a C++ user) I'm not familiar with it. Does it have some advantage over int name = val to counter the disadvantage of requiring more effort to port to a different language?

There's a case to be made for calculating the square root of number outside the loop: firstly on micro-optimisation grounds, but secondly on correctness grounds. div * div could overflow the type.




    // We must print the base-power combinations in sorted order
    sort(prime_factorization.begin(), prime_factorization.end(), [](pair&lt;int, int&gt; p1, pair&lt;int, int&gt; p2) { return p1.first &lt; p2.first; });

    if (okay) {
        cout &lt;&lt; 1 &lt;&lt; '\n';

        for (auto&amp; i : prime_factorization)
            cout &lt;&lt; i.first &lt;&lt; ' ' &lt;&lt; (i.second / m) &lt;&lt; '\n';
    } else
        cout &lt;&lt; 0;



Two things here: firstly, since the sorted values are only needed in one branch of the if it makes more sense to push the sort into that branch. Secondly,

if (test) {
    foo;
} else
    bar;


is easily the weirdest bracing style I've ever seen, and weird style is not good for collaboration. Do you use a company or published style guide?



Finally, my one algorithmic observation.


    // Check if we've already got the base we're trying to add
    auto it = find_if(prime_factorization.begin(), prime_factorization.end(), [&amp;](pair &lt;int, int&gt; p) { return p.first == base; } );

    if (it != prime_factorization.end()) // If yes, add the power to the existing base
        it-&gt;second += power;
    else
        prime_factorization.push_back(make_pair(base, power)); // Else, create a new base



Linear search is never ideal. If you're using a recent standard, std::unordered_map is asymptotically preferable, and also IMO conveys the purpose better. Or maybe you would be better off with std::map, which would remove the need to sort at the end.