Number of integers $n$ between 1 and 1000 such that the HCF of $n$ and $36$ is 1 
How many integers $n$ are there such that $1< n < 1000$ and the highest common factor of $n$ and $36$ is $1$?

I have tried counting the  prime numbers up to $1000$ using the prime-counting function. But there are of course other numbers like $133$, $77$ which are not prime and yet they satisfy the conditions. 
Is there any efficient algorithm to solve this problem?
 A: In order for the greatest common factor of an integer $n$ and $36$ to be $1$, $n$ and $36$ must share no prime divisors.  The prime divisors of $36$ are $2$ and $3$.  
Thus, the question now becomes: 

How many integers $1 \leq n \leq 1000$ are not multiples of $2$ or $3$?

This is fairly easy to compute by looking at the compliment and utilizing the inclusion/exclusion principle --- let $m_k$ be the number of multiples of $k$ between $1$ and $1000$:
\begin{equation}
\mathrm{nonmultiples} = 1000 - \left(m_2 + m_3 - m_6\right)
\end{equation}
It can also be seen that the value of $m_k$ is $\left\lfloor\frac{1000}{k}\right\rfloor$.
A: Since $36 = 2*2*3*3$, $\gcd(n,36) = 1$ iff $n$ is not divisible by $2$ or $3$. Hence 
First we find the number of integers $< 1000$ which are divisible by $2$ or $3$. The we will subtract this number from $999$ to get our required answer.
No. of integers $< 1000$ which are divisible by $2 = [999/2] = 499$
No. of integers $< 1000$ which are divisible by $3 = [999/3] = 333$
But some numbers which are divisible by both $2$ and $3$ i.e. multiples of $6$. So to avoid double counting we need to subtract these multiples of $6$
No. of integers $< 1000$ which are divisible by $6 = [999/6] = 166$
Hence No. of integrs $< 1000$ which have $HCF > 1$ with $36 = 499 + 333 - 166 = 666$
Hence No. of integrs $< 1000$ which have $HCF = 1$ with $36 = 999 - 666 = 333$
