筛法如何高效求欧拉函数？

63.Acwing基础课第874题-简单-筛法求欧拉函数 题目描述 \(给定一个正整数 n，求 1∼n 中每个数的欧拉函数之和\)。 输入格式 \(共一行，包含一个整数 n\)。 输出格式 \(共一行，包含一个整数，表示 1∼n 中每个数的欧拉函数之和。\)。 数据范围 \(1≤n≤10^6\), 输入样例： 6 输出样例： 12 代码： // 包含输入输出流头文件（cin/cout依赖） #include <iostream> // 使用std命名空间，避免重复写std:: using namespace std; // 定义长整型别名：防止求和时溢出（n≤1e6时，欧拉函数和会超出int范围） typedef long long LL; // 常量定义：N=1e6+10，适配题目中n≤1e6的场景 const int N = 1000010; // 全局数组/变量（默认初始化为0/false，无需手动清零） int primes[N]; // primes数组：存储筛选出的所有质数 int cnt; // cnt：记录质数的个数 int euler[N]; // euler数组：euler[i]表示i的欧拉函数值φ(i) bool st[N]; // st数组：标记是否为合数（st[i]=true → i是合数） // 线性筛（欧拉筛）同时求1~n中所有数的欧拉函数值 // 核心：在筛质数的过程中，利用欧拉函数的性质递推计算φ(i) void get_eulers(int n) { // 欧拉函数性质1：φ(1)=1（1与自身互质，1~1中只有1个数） euler[1] = 1; // 遍历2~n的所有数，筛质数+递推欧拉函数 for (int i = 2; i <= n; i ++ ) { // 如果i未被标记（是质数） if (!st[i]) { primes[cnt ++ ] = i; // 存入质数数组 // 欧拉函数性质2：若p是质数，则φ(p)=p-1（1~p中除了p都与p互质） euler[i] = i - 1; } // 遍历已找到的质数，标记合数+递推欧拉函数 for (int j = 0; primes[j] <= n / i; j ++ ) { int t = primes[j] * i; // 当前要标记的合数t = 质数primes[j] × i st[t] = true; // 标记t为合数 // 关键：根据i与primes[j]的整除关系，分两种情况递推φ(t) if (i % primes[j] == 0) { // 情况1：primes[j]是i的质因子（i能被primes[j]整除） // 欧拉函数性质3：若p是质数，且p|i，则φ(i×p) = φ(i) × p euler[t] = euler[i] * primes[j]; break; // 线性筛核心：保证每个合数只被最小质因子筛一次 } // 情况2：primes[j]不是i的质因子（i不能被primes[j]整除） // 欧拉函数性质4：若p是质数，且p不整除i，则φ(i×p) = φ(i) × (p-1) euler[t] = euler[i] * (primes[j] - 1); } } } int main() { int n; // n：输入的上限，要求计算1~n的欧拉函数之和 cin >> n; // 调用函数，筛出1~n的质数并计算所有数的欧拉函数值 get_eulers(n); LL res = 0; // 存储1~n欧拉函数的和，用LL防止溢出 // 累加1~n所有数的欧拉函数值 for (int i = 1; i <= n; i ++ ) res += euler[i]; // 输出最终的和 cout << res << endl; return 0; // 程序正常结束 }