筛法求欧拉函数

目的

求1~N中每个数的欧拉函数

原理

利用线性筛分解质因数的方法

euler[1] = 1;
遍历2 ~ N

• i为质数 euler[i] = i - 1
• i % pj == 0；φ(i * pj) = i * pj * (1 - 1/p1)(1 - 1/p2)...(1 - 1/pk) = pj * ``φ(i)

φ(i) = i * (1 - 1/p1)(1 - 1/p2)...(1 - 1/pk) = pj * ``φ(i)

• i % pj != 0 ；φ(i * pj) = i * pj * (1 - 1/p1)(1 - 1/p2)...(1 - 1/pk) * (1 - 1/pj) = pj * φ(i) * (1 - 1/pj) = (pj - 1) * φ(i)

例题

874. 筛法求欧拉函数

给定一个正整数 n，求 1∼n 中每个数的欧拉函数之和。
输入格式
共一行，包含一个整数 n。
输出格式
共一行，包含一个整数，表示 1∼n 中每个数的欧拉函数之和。
数据范围
1≤n≤106
输入样例：

6

输出样例：

12

时间复杂度：同线性筛法筛质数

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] primers = new int[n];
        int idx = 0;
        boolean[] st = new boolean[n + 1];
        int[] euler = new int[n + 1];
        euler[1] = 1;
        for (int i = 2; i <= n; i++) {
            if (!st[i]) {
                primers[idx++] = i;
                euler[i] = i - 1;
            }
            for (int j = 0; primers[j] <= n / i; j++) {
                st[primers[j] * i] = true;
                if (i % primers[j] == 0) {
                    euler[i * primers[j]] = euler[i] * primers[j];
                    break;
                }
                euler[i * primers[j]] = euler[i] * (primers[j] - 1);
            }
        }
        //注意这里用long类型存储，防止溢出
        long ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += euler[i];
        }
        System.out.println(ans);
    }
}