speeding up nested lcm calculation

Question

How can I speed up this calculation. I have tried some of way to reduce computation but nothing works.

long long pairsFormLCM( int n ) {
    long long res = 0;
    for( int i = 1; i <= n; i++ )
        for( int j = i; j <= n; j++ )
           if( lcm(i, j) == n ) res++; // lcm means least common multiple
    return res;
}

I do not expect any code here. Idea or explanation of solve is required.

Expected run time: O(sqrt(N))

Answer 1

Trying all integer pairs in [1,n] is really overkill. You should factor n and count all products of the factors such that the required multiplicity is achieved by at least one of the products. (The lcm of two integers is the product of all their prime factors, each taken with the largest multiplicity.)

Example:

For n=1500=2².3.5³, the following multiplicities will work:

For 2, 5 combinations: (0,2), (1,2), (2,2), (2,1), (2,0)
For 3, 3 combinations: (0,1), (1,1), (1,0)
For 5, 7 combinations: (0,3), (1,3), (2,3), (3,3), (3,2), (3,1), (3,0)

In total, 5.3.7 = 105 solutions:

(1.1.1,2².3.5³), (2.1.1,2².3.5³), (2².1.1,2².3.5³), (2².1.1,2.3.5³), (2².1.1,1.3.5³),
(1.3.1,2².3.5³), (2.3.1,2².3.5³), (2².3.1,2².3.5³), (2².3.1,2.3.5³), (2².3.1,1.3.5³),
(1.3.1,2².1.5³), (2.3.1,2².1.5³), (2².3.1,2².1.5³), (2².3.1,2.1.5³), (2².3.1,1.1.5³),
(1.1.5,2².3.5³), (2.1.5,2².3.5³), (2².1.5,2².3.5³), (2².1.5,2.3.5³), (2².1.5,1.3.5³),
(1.3.5,2².3.5³), (2.3.5,2².3.5³), (2².3.5,2².3.5³), (2².3.5,2.3.5³), (2².3.5,1.3.5³),
(1.3.5,2².1.5³), (2.3.5,2².1.5³), (2².3.5,2².1.5³), (2².3.5,2.1.5³), (2².3.5,1.1.5³),
(1.1.5²,2².3.5³), (2.1.5²,2².3.5³), (2².1.5²,2².3.5³), (2².1.5²,2.3.5³), (2².1.5²,1.3.5³),
(1.3.5²,2².3.5³), (2.3.5²,2².3.5³), (2².3.5²,2².3.5³), (2².3.5²,2.3.5³), (2².3.5²,1.3.5³),
(1.3.5²,2².1.5³), (2.3.5²,2².1.5³), (2².3.5²,2².1.5³), (2².3.5²,2.1.5³), (2².3.5²,1.1.5³),
(1.1.5³,2².3.5³), (2.1.5³,2².3.5³), (2².1.5³,2².3.5³), (2².1.5³,2.3.5³), (2².1.5³,1.3.5³),
(1.3.5³,2².3.5³), (2.3.5³,2².3.5³), (2².3.5³,2².3.5³), (2².3.5³,2.3.5³), (2².3.5³,1.3.5³),
(1.3.5³,2².1.5³), (2.3.5³,2².1.5³), (2².3.5³,2².1.5³), (2².3.5³,2.1.5³), (2².3.5³,1.1.5³),
(1.1.5³,2².3.5²), (2.1.5³,2².3.5²), (2².1.5³,2².3.5²), (2².1.5³,2.3.5²), (2².1.5³,1.3.5²),
(1.3.5³,2².3.5²), (2.3.5³,2².3.5²), (2².3.5³,2².3.5²), (2².3.5³,2.3.5²), (2².3.5³,1.3.5²),
(1.3.5³,2².1.5²), (2.3.5³,2².1.5²), (2².3.5³,2².1.5²), (2².3.5³,2.1.5²), (2².3.5³,1.1.5²),
(1.1.5³,2².3.5), (2.1.5³,2².3.5), (2².1.5³,2².3.5), (2².1.5³,2.3.5), (2².1.5³,1.3.5),
(1.3.5³,2².3.5), (2.3.5³,2².3.5), (2².3.5³,2².3.5), (2².3.5³,2.3.5), (2².3.5³,1.3.5),
(1.3.5³,2².1.5), (2.3.5³,2².1.5), (2².3.5³,2².1.5), (2².3.5³,2.1.5), (2².3.5³,1.1.5),
(1.1.5³,2².3.1), (2.1.5³,2².3.1), (2².1.5³,2².3.1), (2².1.5³,2.3.1), (2².1.5³,1.3.1),
(1.3.5³,2².3.1), (2.3.5³,2².3.1), (2².3.5³,2².3.1), (2².3.5³,2.3.1), (2².3.5³,1.3.1),
(1.3.5³,2².1.1), (2.3.5³,2².1.1), (2².3.5³,2².1.1), (2².3.5³,2.1.1), (2².3.5³,1.1.1)

There is no need to actually compute the numbers, counting them suffices. More generally, the number of solutions is the product of the multiplicities of all factors of n, each times two plus one.

Beware that some of the solutions are counted twice, by symmetry. This must be fixed.