3
$\begingroup$

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.

  • 0
    @KirkBoyer Yeah, Gerry is right. I want the divisors of$n$that are divisible by k. That is$k$dividing d.2012-09-04

2 Answers 2

5

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.

  • 0
    I got the idea for the above variant also.2012-09-04
1

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,

  • 0
    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.2012-09-04