# Number of Divisor

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.

-
You want divisors $d$ of both $n$ and $k$. Consider what $\gcd(n,k)$ means, and its relationship to each such $d$. Calculating the $\gcd$ is fairly quick. – Kirk Boyer Sep 3 '12 at 22:30
@Kirk, I think sabari wants $k$ dividing $d$, not $d$ dividing $k$. – Gerry Myerson Sep 3 '12 at 23:22
Hm.. from the code he provided I got the impression otherwise (A being the prime-power factors of $n$ and B being the prime-power factors of $k$), although to be honest I don't entirely follow the code, as it is in an unfamiliar language for me. @sabari, can you clarify? – Kirk Boyer Sep 3 '12 at 23:56
@KirkBoyer Yeah, Gerry is right. I want the divisors of n that are divisible by k. That is k dividing d. – sabari Sep 4 '12 at 7:40

Any divisor of $n$ that is itself divisible by $k$ can be written as $d k$, where $d$ is a divisor of $\frac nk$. Hence their number is exactly the number of divisors of $\frac nk$.

Of course we need $k$ to be a divsor of $n$ for this to make sense at all.

-
Thanks a lot! I understood the mistake I made. Out of curiosity , may I ask a small variant of the above.. is it possible to find the "number of divisors of n which are not divisible by k" by simple methods? – sabari Sep 4 '12 at 7:57
I got the idea for the above variant also. – sabari Sep 4 '12 at 8:20

All you have to do is compute $\sigma_0(n/k)$, where $\sigma_0(m)$ is the divisor function, which counts the number of divisors of $m$. The reason of this is that $$k \, | \, m \, | \, n \quad \Longleftrightarrow \quad m = kd \quad \text{and} \quad d \, | \, n/k.$$ This is quite easy to prove, I'll leave it up to you. Now to compute $\sigma_0(n/k)$, one can show that $\sigma$ is a multiplicative function, because $f(n) = 1$ is multiplicative, hence $$\sigma_0(n) = \sum_{d \, | \, n} f(d)$$ also is (well-known theorem in number theory that $\sum_{d \, | \, n} f(d)$ is multiplicative when $f$ is). Therefore, since $\sigma_0(p^{\alpha}) = \alpha+1$, you have $$\sigma_0(n) = \prod_{p \, | , n} (\alpha(n,p) + 1)$$ where $\alpha(n,p)$ stands for the greatest power of $p$ dividing $n$. In other words, all you have to do is factor $n/k$ and use the factorization to compute $\sigma_0(n/k)$.

Hope that helps,

-
$\sigma$ is usually used for the sum of the divisors; $\tau$ or $d$ for the number of divisors. – Gerry Myerson Sep 3 '12 at 23:23
Right ; I forgot to write $\sigma_0$. The function $\sigma_k$ is usually for the sum of the $k^{\text{th}}$ powers. Thanks for noticing. – Patrick Da Silva Sep 4 '12 at 2:55