Finally I solved it . From seeing your code I can guess that you are constructing all pairs of integers whose LCM is n . But the problem is that there are an exponential number of possibilities .

My approach was the following , first notice that p and q are always the divisors of n also you can create equivalence classes for p . If n = p₁^pow₁ * ...p_k^pow_k is the prime factorisation of n , then we partition all the divisors into equivalence classes such that a particular equivalence class contains a subset of prime divisors to their highest power and other prime divisors can have smaller powers . For each of the equivalence class in p we consider how many numbers q can be created such that lcm(p, q) = n .

This is the abstract of my approach , Take a look at my CODE