Counting square free numbers $\le N$ is a classical problem which can be solved using inclusion-exclusion problem or using Möbius function (http://oeis.org/A071172).
I want to count square free numbers which are co-prime to a given number $m$ within a limit. Let $C(N, m)$ = no. of square free numbers $\le N$ and co-prime to $m$.
Example: $C(10,2)=4$ [4 such numbers are 1, 3, 5, 7]
How can I compute this for any $m$ efficiently?
As mentioned in the comment, $$C(N,m)=\sum_{n=1}^{N}\mu^{2}(n)(1-sgn(gcd(m,n)-1))$$ Where $\mu (n)=$ Möbius function, $sgn()=$ Sign function.
Can you calculate the sum in $O(\sqrt n)$? Or maybe using inclusion-exclusion principle?
What follows does not match the question exactly but may be interesting to know.
Observe that the Dirichlet series of the indicator function of squarefree numbers is $$L(s) = \prod_p \left(1+\frac{1}{p^s}\right).$$
If these are supposed to be co-prime with $m$ we get $$L(s) = \prod_{p|m} \frac{1}{1+\frac{1}{p^s}} \prod_p \left(1+\frac{1}{p^s}\right).$$
This is $$\prod_{p|m} \frac{1}{1+\frac{1}{p^s}} \prod_p \frac{1-1/p^{2s}}{1-1/p^s} \\ = \prod_{p|m} \frac{1}{1+\frac{1}{p^s}} \frac{\zeta(s)}{\zeta(2s)}.$$
With the dominant pole at $s=1$ being simple we have by the Wiener-Ikehara theorem for the number of squarefree positive integers co-prime to $m$ the asymptotic
$$\sum_{n\le x, \; \gcd(m,n)=1, \; p^2\not\mid n} 1 \sim \prod_{p|m} \frac{1}{1+\frac{1}{p}} \frac{1}{\zeta(2)} x \\ = \frac{6}{\pi^2} x \prod_{p|m} \frac{1}{1+\frac{1}{p}} \\ = \frac{6}{\pi^2} x \prod_{p|m} \frac{p}{p+1}.$$
This approximation is remarkably accurate. For example it gives for $x=3000$ and $m=6$ the value $911.8906524$ while the correct answer is $911.$ For $x=4000$ and $m=10$ it gives $1350.949114$ with the correct answer being $1349.$ Finally for $x=5000$ and $m=30$ we get $1266.514795$ with the correct answer being $1267.$