Finding all pairs of numbers that equals an equation

algorithm, c++, math

Solution

The problem is to find all pairs of positive integers `(a,b)` that satisfy the equation `a^2 * b = c` where `c` is also a positive integer.

From the equation, `c` is divisible by a perfect square. So first, we find all perfect squares that divide `c` evenly. Trivially, `a=1, b=c` satisfies this, so we know that every value of `c` has at least one solution. After finding every `a`, we divide `c` by each of the `a^2` to yield its corresponding `b`.

Here's the above implemented in C++:

std::vector<std::pair<int, int> > solve(int c) {
    std::vector<int> a;
    for (int i = 1; i * i <= c; ++i)
        if (c % (i*i) == 0) a.push_back(i);

    std::vector<std::pair<int, int> > solutions;
    solutions.reserve(a.size());
    for (std::vector<int>::iterator it = a.begin(); it != a.end(); ++it) {
        const int& a = *it;
        solutions.push_back(std::pair<int, int>(a, c / (a*a)));
    }

    return solutions;
}

Here's a live example, showing solutions for `c = 7! = 5040`.

Problem

What would be the most optimal method in c++ to discover all pairs of positive integer numbers that fit a formula. For example: ``` a^2 * b = 16;//a & b MUST be positive INT. ``` How could I find all the combinations of a and b that will fit the formula? Edit: For more clarity, this is just an example. Really I have a^2 * b = c where c is incrementing using a for loop and I need to find every positive integer pair (a,b) that will fit the criteria of this equation.

Original source