Counting square free numbers co-prime to $m$ 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?
 A: 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.$
A: 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$
