How many numbers in a given range are coprime to $N$? Is there a good algorithm for counting the numbers $x$ between $A$ and $B$ with $x$ and $N$ coprime? This is just like this question except for the range.
The factorization of $N$ is known. I actually need to solve the problem for fixed $N$ and many ranges, so I think I can mark all multiples of factors of $N$ in a BitSet and simply count what remains. But is there a nicer solution (or one for the case I need the answer for a single range only)?

For a proof of André Nicolas's formula using multiplicative number theory, see Section 8.3 in I. Niven, H. S. Zuckerman, H. L. Montgomery, An Introduction to the Theory of Numbers, 5th ed., Wiley (New York), 1991, which gives the succinct expressions
\begin{align}
f(C) & = \sum_{d|N} \mu(d) \left\lfloor \frac{C}{d} \right\rfloor\\
     & = \frac{C \varphi(N)}{N} - \sum_{d|N} \mu(d) \text{ frac} \left( \frac{C}{d} \right)
\end{align}
where the sums are taken over the positive square-free integers $d$ that divide $N$ because $\mu(d)$, the Möbius function, is $0$ when $d$ is not square-free, and $\text{frac}$ is the fractional part function.  We see that $C\varphi(N)/N$ approximates $f(C)$ and that the approximation improves as $C$ increases or as the number of prime factors of $N$ decreases.
