Combitronics and Prime Factorization : Calculate num of Pairs of (m,n) where GCD(m,n)=x

Question

Calculate num of Pairs of (m,n) where GCD(m,n)=x, say x=1 and 1<=m<=M=10^5 and 1<=n<=N=10^5.

M and N will be given

I know we can use (Brute Force) 2 iterators to iterate through M and N and with a check to the GCD being ==1 increment the number of possible pairs.

But that works only for smaller numbers and for larger ones it takes hell hell hell a lot of time. Like M = 100000 and N =100000

There is a way where we can use the prime factors to calculate.

Note: I just want the number of possible pairs and not the pairs.

Answer 1

Let's start with your brute force algorithm:

for (n = 1; n <= N; n++) {
    for (m = 1; m <= M; m++) {
        if (gcd(m, n) == x) count++;
    }
}

You can speed this up when your x is greater than 1, because if the gdc of n and m is x, these numbers themselves must be multiples of x:

for (n = x; n <= N; n += x) {
    for (m = x; m <= M; m += x) {
        if (gcd(m, n) == x) count++;
    }
}

In these loops, we can divide all numbers by x:

int NN = N / x;
int MM = M / x;

for (n = 1; n <= NN; n++) {
    for (m = 1; m <= MM; m++) {
        if (gcd(m, n) == 1) count++;
    }
}

Checking for a gdc of 1 is a test for coprime pairs. A bit of research leads to Wikipedia and turns up a neat (and lavishly illustrated) algorithm to generate all coprime pairs:

#define NN (N / X)
#define MM (M / X)

void spread(int m, int n, int *count)
{
    if (n > NN) return;
    if (m > MM) return;

    if (n != m && m <= NN) (*count)++;
    (*count)++;

    spread(2*m - n, m, count);
    spread(2*m + n, m, count);
    spread(m + 2*n, n, count);
}

int main()
{
    int count = 1;

    spread(2, 1, &count);
    spread(3, 1, &count);

    printf("%d\n", count);

    return 0;
}

The count starts at 1, because the pair generator doesn't generate (1, 1), which also matches your criterion. The code works if your M is greater than or equal to N. If not, swap them.

This bottom-up approach is much faster than the loops in the same way that the Sieve of Erathostenes is faster than doing naive primality checks for a range of numbers.

I'm afraid this is C, not Java. The count is passed as pointer; I guess the Java idiom might be a reference. You could also return the count from spread and accumulate, of course. (And it would be nice if N, NN and so on weren't globals, but I'm sure you'll wrap a nice, tidy class around that in Java.)

Edit: The code above is recursive and requires a lot of stack space. You can migrate the required space from the stack to the heap if you linearise the code and use a queue. The code then look like this:

int spread(m, n)
{
    Queue q;
    int count = 1;

    q.push(m, n);

    while (!q.empty()) {
        int m, n;

        q.pull(&m, &n);

        if (n <= NN && m <= MM) {
            if (n != m && m <= NN) count++;
            count++;

            q.push(2*m - n, m);
            q.push(2*m + n, m);
            q.push(m + 2*n, n);
        }
    }

    return count;
}

int main()
{
    Queue q;
    int count = 1;

    count += spread(2, 1);
    count += spread(3, 1);

    printf("%d\n", count);

    return 0;
}

It will take fairly long to run if your M and N go beyond 100,000. But you can easily parallelise it, because the (2, 1) and (3, 1) cases are independent.