时间复杂度

O(n)

java代码

import java.util.*;
class Main{
    static int n = 0, N = 1000010;
    static int[] phi = new int[N];//存储数字n的质数的个数
    static int[] primes = new int[N];//存储质数的下标对应的质数
    static int cnt = 0;//存储质数的下标
    static boolean[] st = new boolean[N];//标示n有没有被筛掉
    static long euler(int n){
        phi[1] = 1;//从定义出发
        for(int i = 2; i <= n; ++i){
            if(!st[i]){
                primes[cnt++] = i;//质数的集合
                phi[i] = i - 1;//如果i是质数，那么与它互质的个数是i - 1
            }
            for(int j = 0; primes[j] <= n / i; ++j){
                st[primes[j] * i] = true;//筛掉prrmes[j]的倍数
                if(i % primes[j] == 0){//如果primes[j] 与i不互质，表示primes[j]是i的一个质因子，i的欧拉函数中包含primes[j]，然后根据定义得到下列公式
                    phi[primes[j] * i] = primes[j] * phi[i];
                    break;//剪枝
                }
                //如果primes[j] 与i互质，表示primes[j]不是i的一个质因子，i的欧拉函数中不包含primes[j]，然后根据定义得到下列公式
                phi[primes[j] * i] = (primes[j] - 1) * phi[i];
            }
        }
        long res = 0;
        for(int i = 1; i <= n; ++i){
            res += phi[i];
        }
        return res;
    }

    public static void main(String[] args)throws Exception{
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        System.out.print(euler(n));
    }
}