A Graph Theoretic Formula for the Number of Primes $\pi (n)$

R. Jacobs, C. E. Larson

Let PR$[n]$ be the graph whose vertices are $2,3,\dots ,n$ with vertex $v$ adjacent to vertex $w$ if and only if $\gcd (v,w)>1$. It is shown that $\pi (n)$, the the number of primes no…