%I #14 Feb 03 2018 12:10:29
%S 1,2,3,3,4,3,4,4,4,3,4,4,5,4,4,4,5,5,6,6,6,5,6,6,6,5,5,5,6,6,7,7,7,6,
%T 6,6,7,6,6,6,7,7,8,8,8,7,8,8,8,8,8,8,9,9,9,9,9,8,9,9,10,9,9,9,9,9,10,
%U 10,10,10,11,11,12,11,11,11,11,11,12,12,12,11,12,12,12,11,11,11,12,12,12,12,12,11,11,11,12
%N a(n) is the number of connected components in the graph with vertices 1..n and adjacency criterion i and j not coprime.
%F a(n) = 1 + pi(n) - pi(n / 2) + [n >= 4], where pi denotes the prime counting function (A000720, generalized to reals), and [] the Iverson bracket.
%t A[n_] := Length[
%t ConnectedComponents[
%t AdjacencyGraph[Map[Boole[# != 1] &, Array[GCD, {n, n}], {2}]]]]
%t Table[A[n], {n, 1, 107}]
%o (PARI) a(n) = 1 + primepi(n) - primepi(n / 2) + (n >= 4); \\ _Michel Marcus_, Jan 09 2018
%Y Cf. A000720.
%K nonn
%O 1,2
%A _Luc Rousseau_, Jan 01 2018