[Math] Counting Coprime Numbers in a range:

Question

I know that $\varphi(n)$ is the number of positive integers less than $n$ that are coprime to $n$. What I don't know is how to solve a related, but seemingly reverse problem.

How do I count the number of integers coprime to $n$ in a range $\left[a,b\right]$ where $n < a < b$?

I know that I can take the prime divisors of $n$ and do some inclusion-exclusion action on the values $a$ and $b$ to count but I'm wondering if there isn't a better method. If $n$ is smooth, this can get rather lengthy.

Comments??

Thanks!

Answer 1

I think that this solution should be better than inclusion-exclusion, what about you take primes from factorization of n and run Eratosthene's sieve on $[a,b]$ using just these primes?