Counting integers $n \leq x$ such that $rad(n)=r$ Let $r$ be the largest square-free integer that divides $n$. Then $$r = \operatorname{rad}(n)=\prod_{\substack{p\mid n\\p\text{ prime}}}p$$ $r$ is called the "radical" of $n$, or the square-free kernel. Have also seen the term "core". For a given square-free $r$ and integer $x$, my question is how many integers $n\leq x$ exist such that $\operatorname{rad}(n) = r$. For example with $r=15$, and $x=100$, then $15,45,75$ are the only $3$ such integers. I haven't found any formula or algorithm in the literature that seems useful here, for generic $r$ and $x$.
 A: In general I think this is hard. But, you can look at the following algorithm:
Factor $r$ into primes as: $r = p_1 \cdots p_k$.
Note that $\text{rad}(n) = r \iff n = p_1^{a_1} \cdots p_k^{a_k}$ for some integers $a_i$.
To determine the number of $(a_1, \dots , a_k)$ such that $n \leq x$ we can count the solutions $(a_1, \dots , a_k)$ of $a_1 \log(p_1) + \dots + a_k \log(p_k) \leq \log(x)$.
If $r$ is prime, then the number of solutions can be determined very efficiently. If $r$ is not prime ($k > 1$), then this is more difficult.
You can do it somewhat efficiently by looping over the $a_i$ and and by stopping early if the sum $a_1 \log(p_1) + \dots + a_k \log(p_k)$ exceeds $\log(x)$.
One other way is to note that the vectors $v_i = (0, \dots , \log(a_i), \dots , 0)$ for $1 \leq 1 \leq k$ span a lattice.
We are asking for the number of lattice points inside the convex set defined by $a_1 \log(p_1) + \dots + a_k \log(p_k) \leq \log(x)$.
Perhaps a more efficient algorithm can be found that way.
