A visible point is a point $(a, b)\in \mathbb{Z}^2,$ with $gcd(a,b)=1.$ It is well-known that the number $V(N)$ of visible points with $0<a, b \leq N$ is asymptotic to $N^2/\zeta(2),$ but suppose I really want to compute it exactly. Can it be done in polynomial time (polynomial in $\log N,$ that is)? If one wants to be more modest, can it be computed in time sublinear in $N?$ Or even linear in $N?$ It can be computed in time $O(N^{1+\epsilon}),$ for any $\epsilon>0,$ since we can compute the totient function in sub-polynomial time.

A visible point is a point $(a, b)\in \mathbb{Z}^2,$ with $gcd(a,b)=1$. It is well-known that the number $V(N)$ of visible points with $0<a, b \leq N$ is asymptotic to $N^2/\zeta(2)$, but suppose I really want to compute it exactly. Can it be done in polynomial time (polynomial in $\log N,$ that is)? 

If one wants to be more modest, can it be computed in time sublinear in $N?$ Or even linear in $N?$ It can be computed in time $O(N^{1+\epsilon})$, for any $\epsilon>0$, since we can compute the totient function in sub-polynomial time.