$$\color{Red}{筛法求欧拉函数(详解):从线性筛法升级到筛欧拉函数}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

给定一个正整数 n，求 1∼n 中每个数的欧拉函数之和。

输入格式

共一行，包含一个整数 n。

输出格式

共一行，包含一个整数，表示 1∼n 中每个数的欧拉函数之和。

数据范围

1 ≤ n ≤ 10 ^ 6

输入样例：

6

输出样例：

12

线性筛法：
怎样才能避免重复筛选呢？
如果我们每次筛到一个质数，只需要把小于它的最小质因子的数与它相乘的数锁定，那么就是唯一的锁定方式了。
那么为什么可以这样？
我们可以把我们每次筛到的数字i当成一个倍数，然后用j每次从小到大遍历目前已经筛到的质数，若i % primes[j] != 0，因为质数是从小到大遍历，不满足这个，说明pj目前小于i的最小质因子。那么pj * i的最小质因子显然根据算数基本定理，应该是pj。
若i % primes[j] == 0，说明此时pj是i的最小质因子，所以i能被拆分成pj乘以它别的质因数的形式,那么pj * i的最小质因子显然应该也是pj。

我们每次就按这个点，找到每个数的最小质因子pj然后再把它乘i的倍数筛除，保证能只筛倒它一次（最小质因子只有一个）。

然后在pj刚好为i的最小质因子的时候break（再大pj可能就不是pj * i的最小质因子了。

void is_primes(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!st[i])  primes[cnt++] = i;
        //遍历n内部的最小质数
        for(int j = 0; primes[j] <= n / i; j ++)
        {
            //此时pj为pj * i的最小质因子，筛除它i倍数的数
            st[primes[j] * i] = true;
            //此时pj为i的最小质因子，再大下去没有意义，后续更大的因子i会遍历乘到它
            if(i % primes[j] == 0) break;
        }
    }
}

如何把线性筛法升级到求欧拉函数

首先，我们线性筛法是优化了筛质数的过程，保证了每个数的筛除都只会被筛除一次。

那么我们就在其中进行欧拉函数的判断。

首先，当一个数是质数的情况下，即 !st[i]时，质数i的欧拉函数显然是 1 -> i - 1

其次，在筛除过程中，我们会对 prime[j] * i这个数，进行判断筛除。

①当i % primes[j] == 0时

primes[j]为i的最小质因数，那么primes[j] * i这个数的最小值质因数显然也是primes[j]，一个数字的欧拉函数除了N的倍数部分，后面乘积部分显然只和它的最小质因子有哪些有关，一个数乘以它的质因数，显然乘积的数，不会增加质因子

那么显然，对于乘积这个数的欧拉函数，它仅仅是倍数发生变化，故phi[i * primes[j]] = primes[j] * phi[i]

②当i % primes[j] != 0时

显然此时primes[j]此时比i的最小质因数小，故它们的乘积的最小质因数，应该是primes[j]，那么根据第①项的推导，此时比起i，乘积应该比起i多了一个最小质因数，也就是primes[j]，故欧拉函数除了倍数变了，后面乘积项应该也多了1 - 1 / primes[j]

故 phi[primes[j] * i] = primes[j] * phi[i] * (1 - 1 / primes[j]) = phi[i] * (primes[j] - 1)

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int n, cnt, N = 1000010;
    static int[] primes = new int[N];
    static boolean[] st = new boolean[N];
    static int[] phi = new int[N];
    static long res = 0;

    static void get_euler(int n) {
        phi[1] = 1;
        for (int i = 2; i <= n; i++) {
            if (!st[i]) {
                primes[cnt++] = i;
                phi[i] = i - 1;
            }
            for (int j = 0; primes[j] <= n / i; j++) {
                st[primes[j] * i] = true;
                if (i % primes[j] == 0) {
                    phi[i * primes[j]] = phi[i] * primes[j];
                    break;
                }
                phi[i * primes[j]] = phi[i] * (primes[j] - 1);
            }
        }
    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        get_euler(n);
        for (int i = 1; i <= n; i++) res += phi[i];
        System.out.println(res);
    }
}