3-筛法求欧拉函数

算法思想

算法模板

import java.util.*;

public class Main {
    static int N = 1000010;
    // euler[i]存储 i 的欧拉函数
    static int[] euler = new int[N],
        primes = new int[N];
    static int cnt;
    static boolean[] st = new boolean[N];
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        getEulers(n);
        long res = 0;
        for(int i = 1; i <= n; i ++ ) res += euler[i];
        
        System.out.println(res);
    }
    
    public static void getEulers(int n)
    {
        euler[1] = 1;
        for(int i = 2; i <= n; i ++ )
        {
            if(!st[i])
            {
                primes[cnt ++] = i;
                // i 为质数，显然 1 ~ i - 1 均与 i 互质
                // i 的互质数的数量为 i - 1
                euler[i] = i - 1;
            }
            
            for(int j = 0; primes[j] <= n / i; j ++ )
            {
                int t = primes[j] * i;
                st[t] = true;
                
                if(i % primes[j] == 0)
                {
                    // i = k * primes[j]
                    // t = i * primes[j] = k * primes[j] ^ 2
                    // 所以 i 和 t 有相同的质因子
                    euler[t] = euler[i] * primes[j];
                    break;
                }
                
                // i % primes[j] != 0
                // 利用积性函数性质，可得出下述式子
                euler[t] = euler[i] * (primes[j] - 1);
            }
        }
    }
}

参考资料

1. G09 筛法求欧拉函数_哔哩哔哩_bilibili