欧拉函数变形

$GCD(x,y) == prime$ 则 $ \lfloor GCD(x,y) \div prime \rfloor == 1$

则转换为求欧拉函数。此时只需要将上限整体往下压缩prime则可以求互质区间

关于是否会重复：每一个素数都是为一的，说明每一个互质数对应乘上该素数也是唯一的

python版本

def getPrimes(n):
    #phi[1] = 1 #默认0与1互质
    for i in range(2,n+1):
        if vis[i] == False:
            primes.append(i)
            phi[i] = i - 1
        j = 0
        while primes[j]*i <= n:
            vis[primes[j]*i] = True
            phi[primes[j]*i] = (primes[j] - 1)*phi[i]
            if i % primes[j] == 0:
                phi[primes[j]*i] = primes[j]*phi[i]
                break
            j += 1

n = int(input())
vis = [False]*(n + 1)
primes = []
phi = [0]*(n + 1)
getPrimes(n)

pre = [0]*(n+1)
for i in range(1,n+1):
    pre[i] = pre[i - 1] + phi[i]

res= 0 

for i in range(len(primes)):
    res += pre[n // primes[i]]*2 + 1


print(res)