pts[n_]:=Select[Tuples[Range[n],2],CoprimeQ@@#&];

{len,tour}=FindShortestTour[pts[10],Method->"Greedy"]
{44+22 (Sqrt[2])+2 (Sqrt[10]),{1,11,16,23,28,36,39,48,53,60,54,61,55,56,50,43,44,51,57,62,58,63,59,52,46,47,45,38,33,34,35,27,22,15,9,10,8,7,14,20,26,32,37,42,41,49,40,29,30,31,25,19,18,24,17,12,3,4,5,13,6,21,2}}
ListLinePlot[pts[10][[tour]],Mesh->All,PlotLabel->N[len]]

{len,tour}=FindShortestTour[pts[10],Method->"TwoOpt"]
{74.5269119345812`,{1,11,17,16,23,28,29,30,24,18,19,25,31,37,42,41,40,36,39,48,53,60,61,54,49,55,56,50,43,44,51,57,62,58,63,59,52,47,46,45,38,33,32,26,20,21,34,35,27,22,15,10,9,8,14,7,6,13,5,4,12,3,2}}
ListLinePlot[pts[10][[tour]],Mesh->All,PlotLabel->N[len]]

{len,tour}=FindShortestTour[pts[10],Method->"SimulatedAnnealing"]
{38+25 (Sqrt[2]),{49,41,40,36,39,48,53,60,54,61,55,56,50,44,51,57,62,58,63,59,52,47,46,45,38,34,35,27,22,15,10,9,8,7,6,14,20,21,26,33,32,25,19,18,13,5,4,12,3,2,1,11,17,16,23,28,29,24,30,31,37,43,42}}
ListLinePlot[pts[10][[tour]],Mesh->All,AxesOrigin->{0,0},PlotLabel->N[len]]