I am looking for an efficient way to count the number of coprime vectors in a finite and bounded set of integer vectors.
The vectors in my set are $N$-dimensional integer vectors whose components are bounded on the top and bottom by an arbitrary value $K$. Let $x = [x_1,x_2,\ldots,x_N]$ denote a vector from this set. Then $x$ is coprime if the greatest common denominator of all its elements is 1. That is, $\gcd(x_1,x_2,...,x_N)=1$.
Some 3-dimensional coprime vectors include: $x = [1,2, 3] , [6, 10, 15] ,[0, 1, 1]$
Some 3-dimensional non-coprime vectors include: $x = [2,4,6] ,[0, 10, 15] ,[0, 12, 12]$
For fixed $N$ and $K$, my set contains a total of $(2K+1)^N$ distinct integer vectors as each of the $N$ elements can take on integer values from $-K,\ldots,0,\ldots,K$. A brute-force approach for counting the number of coprime vectors consists of iterating over each of the $(2K+1)^N$ possible vectors and checking to see whether they are coprime (using, for instance, this function). Unfortunately, this approach quickly runs into time and memory issues for large values of $N$ and $K$.
I am wondering if anyone can think of a way to smart algorithm to do this. Ideally, I am looking to implement this algorithm as a MATLAB function that can number of coprime pairs given $N$ and $K$ as its input.