Найти вероятность того, что два случайно выбранных целых числа (из n целых) будут относительно простыми

Я столкнулся с проблемой нахождения указанной вероятности, и моей первой попыткой было придумать следующий алгоритм: я считаю количество пар, которые являются относительно простыми.

int rel = 0
int total = n * (n - 1) / 2
for i in [1, n)
    for j in [i+1, n)
        if gcd(i, j) == 1
            ++rel;
return rel / total

, что составляет O (n ^ 2) .

Вот моя попытка уменьшить сложность:

Наблюдение (1): 1 является относительно простым с [2, n] , поэтому n - 1 пары являются тривиально.

Наблюдение (2): 2 не является относительно простым с четными числами в диапазоне [4, n] , поэтому оставшиеся нечетные числа относительно просты с 2, поэтому

 #Relatively prime pairs = (n / 2) if n is even 

                         = (n / 2 - 1) if n is odd.

Итак, мои улучшенные алгоритм будет выглядеть следующим образом:

int total = n * (n - 1) / 2
int rel = 0
if (n % 2) // n is odd
    rel = (n - 1) + n / 2 - 1
else // n is even
    rel = (n - 1) + n / 2

for i in [3, n)
    for j in [i+1, n)
        if gcd(i, j) == 1
            ++rel;
return rel / total

При таком подходе я мог бы сократить два цикла, но сложность времени наихудшего случая все еще O (n ^ 2) .

Вопрос: Мой вопрос: можем ли мы использовать какие-либо математические свойства, кроме указанных выше, чтобы найти желаемую вероятность в линейном времени?

Спасибо.