Question: 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?

Answer: 
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](https://en.wikipedia.org/wiki/Wiener%E2%80%93Ikehara_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.$
As part of working on a particular Project Euler problem, the following Python code does something similar to what you need, although instead of counting co-primality to $m$, it counts those square-free numbers that are a multiple of $m$ in $\mathcal{O}(\sqrt(n))$ time:

```
def sieveMoebius(lim):
    ''' Calc moebius(k) for k in range(0, lim+1) '''
    sieve = [None for i in range(lim+1)]
    sieve[0] = 0
    sieve[1] = 1
    for i in range(2, lim+1):
        if sieve[i] is None:
            for j in range(i, lim+1, i):
                sieve[j] = 1 if sieve[j] is None else (-1 * sieve[j])
            ii = i * i
            for j in range(ii, lim+1, ii):
                sieve[j] = 0
    return sieve

def countRadicalsWithSpecifiedFactors(N, primeFactors):
    r = int(N**0.5)
    prodOfFacs = reduce(mul, primeFactors, 1)
    sieve = sieveMoebius(r)
    return sum(((sieve[k] * ((N//(k*k)) if not k % prodOfFacs else (N//(prodOfFacs*k*k)))) for k in range(1,r+1) ))

```

For $m$ prime, this helps answer OP's question, as you subtract the result of this function from the number of square free primes $\le N$