【题目来源】
AcWing：874. 筛法求欧拉函数 - AcWing题库
【题目描述】
给定一个正整数 \(n\)，求 \(1\sim n\) 中每个数的欧拉函数之和。
【输入】
共一行，包含一个整数 \(n\)。
【输出】
共一行，包含一个整数，表示 \(1\sim n\) 中每个数的欧拉函数之和。
【输入样例】
6
【输出样例】
12
【解题思路】
【算法标签】
《AcWing 874 筛法求欧拉函数》 #数学知识# #欧拉函数# #线性筛法#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 1000005; // 定义常量 N，表示最大范围
int primes[N], cnt; // primes 数组存储质数，cnt 表示质数的数量
int phi[N]; // phi 数组存储欧拉函数值
bool st[N]; // st 数组标记是否为合数
long long ans = 0; // ans 用于存储欧拉函数的累加和// 筛法求质数并计算欧拉函数
void get_primes(int n)
{phi[1] = 1; // 初始化 phi[1] = 1for (int i = 2; i <= n; i++) { // 遍历 2 到 n 的所有整数if (st[i] == false) { // 如果 i 是质数primes[cnt++] = i; // 将 i 加入质数数组phi[i] = i - 1; // 质数的欧拉函数值为 i - 1}for (int j = 0; primes[j] <= n / i; j++) { // 筛去 i 的倍数st[primes[j] * i] = true; // 标记 primes[j] * i 为合数if (i % primes[j] == 0) { // 如果 i 能被 primes[j] 整除phi[primes[j] * i] = phi[i] * primes[j]; // 更新欧拉函数值break; // 跳出循环}phi[primes[j] * i] = phi[i] * (primes[j] - 1); // 更新欧拉函数值}}for (int i = 1; i <= n; i++) ans += phi[i]; // 累加欧拉函数值
}int main()
{int n; // 定义整数 ncin >> n; // 输入整数 nget_primes(n); // 调用筛法求质数并计算欧拉函数cout << ans << endl; // 输出欧拉函数的累加和return 0; // 程序结束
}
【运行结果】
6
12