0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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)$

$\endgroup$
  • $\begingroup$ So basically, divide away as many factors $d$ as you can, then count the number of divisors of whatever's left. $\endgroup$ – Arthur Oct 21 '17 at 8:14
  • $\begingroup$ @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? $\endgroup$ – someone123123 Oct 21 '17 at 8:16
  • $\begingroup$ @someone123123 That's what Siong wrote in formulas and I wrote in words, yes. $\endgroup$ – Arthur Oct 21 '17 at 8:17
  • 1
    $\begingroup$ I got it now, thanks for your answers. $\endgroup$ – someone123123 Oct 21 '17 at 8:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.