Figure all combinations of two integers of a product

Question

example: all combinations of two integers whose product is 36

output:

1*36, 2*18, 3*12, 4*9, 6*6 etc..

I found this question on a book a while ago and I can't think of an approach. Please suggest the approach/code for this problem.

Possible duplicate of [Efficiently getting all divisors of a given number](https://stackoverflow.com/questions/26753839/efficiently-getting-all-divisors-of-a-given-number) — Retired Ninja, Feb 19 '19 at 00:38
How about this inefficient approach: `for (int x = 0; x <= 36; ++x) for(int y = 0; y <= 36; ++x) if (x * y == 36) cout << x << ' ' << y << '\n';` — Eljay, Feb 19 '19 at 00:47

Kunal Puri · Accepted Answer · 2019-02-19T01:33:31.400

You may do something like this:

#include <iostream>

int main()
{
    int n = 36;
    int biggestDivisor = n; // in case n is prime number, biggestDivisor is n

    for (int i = 1; i < biggestDivisor; i++) {
        if (n % i == 0) {
            std::cout << i << "*" << n / i << " ";
            biggestDivisor = n / i; // done so as to prevent 9 * 4 from getting printed if 4 * 9 is printed
        }
    }
}

Please note that the above approach works for all n > 1.

As per my understanding, you didn't want to print 9 * 4, in case 4 * 9 is already printed.

If you want to print all pairs, then do this:

#include <iostream>
#include <set>

int main()
{
    int n = 36;
    int biggestDivisor = n;

    std::set<std::pair<int, int> > combinationsList;

    for (int i = 1; i < biggestDivisor; i++) {
        if (n % i == 0) {
            combinationsList.insert(std::make_pair(i, n / i));
            combinationsList.insert(std::make_pair(n / i, i));
            biggestDivisor = n / i;
        }
    }

    for (const auto &ele: combinationsList) {
        std::cout << ele.first << "*" << ele.second << " ";
    }
}

Figure all combinations of two integers of a product

1 Answers1