# Fastest way to count divisors of number that are not divisible by one prime number.

Let's define function $f(x,d)$ to be the number of divisors of $x$ that are not divisible by $d$ , and $d$ is prime number. What is the fastest way to count those divisors for given $x$ and $d$.

For example: Let's say $x = 6, d = 3, f(6, 3) = 2$, divisors of $x$ are $\{1, 2, 3, 6\}$, but we are not counting $3, 6$ because they are divisible by $d$.

I got the idea that in $\sqrt{x}$ steps we can loop all the divisors of $x$ and check if they are divisible by $d$. But I was thinking that this could be done faster. Can you give me some hints where to start?

## 1 Answer

Let $x=d^lk$ where $\gcd(d,k)=1$.

Then consider prime factorization of $k=\prod_{i=1}^m p_i^{n_i}$.

then the mumber of such divisors would be equal to $\prod_{i=1}^m(n_i+1)$

• So basically, divide away as many factors $d$ as you can, then count the number of divisors of whatever's left. – Arthur Oct 21 '17 at 8:14
• @Arthur so for example for 6 and $d = 3$, we would divide 6 by three once, and then count the divisors of 2, and the result would be two? – someone123123 Oct 21 '17 at 8:16
• @someone123123 That's what Siong wrote in formulas and I wrote in words, yes. – Arthur Oct 21 '17 at 8:17
• I got it now, thanks for your answers. – someone123123 Oct 21 '17 at 8:18