Here's a more general version of your problem. It can be solved using Mobius Inversion that is beautifully explained in this blog post. There's also the solution to the problem in the comments section of the post.

The way I like to do it is to calculate the number of ordered pairs (x, y) such that a ≤ x ≤ b, c ≤ y ≤ d and gcd(x, y) > 1, this is the opposite of co-prime pairs.

What you do is that you start out by counting the number of pairs that have even gcd, then continue with counting the number of pairs which are divisible by 3, then the number of pairs that are divisible by 5 and so on.

Problem is that you've now over-counted as there are pairs with gcd divisible by both 2 and 3, so subtract the number of pairs divisible by 6, and do the same for 10 and so on.

But now you have under-counted as there are pairs with gcd divisible by 2,3 and 5, so add the number of pairs divisible by 30.

And so on ...

This is actually just the inclusion-exclusion principle. Lets think about what we did. For numbers n that contained an odd number of unique prime factors we added the count of all pairs with gcd divisible by n. For numbers n that contains an even number of unique prime factors we subtracted all pairs. For all other n, for example n = 4, we didn't do anything.

So for each n we either use  + ,  -  or 0. There is name for this, it is called the Möbius function μ. Only difference is that it is defined  -  what we want, so lets use  - μ.

Final formula: Number of ordered pairs (x, y) such that a ≤ x ≤ b, c ≤ y ≤ d and gcd(x, y) > 1 is

(# of pairs (x, y) such that their gcd is divisible by n).