How to find the Number of divisors of a number 'n' that are also divisible by another number 'k' without looping through all the divisors of n? I tried the following:
Stored powers of all prime factors of n in an associative array A and did similarly for k, stored the powers of all primes factors in array B.
ans = 1
for a in A: // Here a is the prime factor and A[a] gives its power
ans *= if( a is present in B ) ? 1 : A[a] + 1
print ans
Note : It is not homework.