【题目来源】
AcWing：873. 欧拉函数 - AcWing题库
【题目描述】
给定 \(n\) 个正整数 \(a_i\)，请你求出每个数的欧拉函数。
【输入】
第一行包含整数 \(n\)。
接下来 \(n\) 行，每行包含一个正整数 \(a_i\)。
【输出】
输出共 \(n\) 行，每行输出一个正整数 \(a_i\) 的欧拉函数。
【输入样例】
3
3
6
8
【输出样例】
2
2
4
【解题思路】
【算法标签】
《AcWing 873 欧拉函数》 #数学知识# #欧拉函数#
【代码详解】
#include <bits/stdc++.h>
using namespace std;// 定义欧拉函数，计算小于等于n且与n互质的数的个数
int oula(int n)
{int res = n; // 初始化结果为nfor (int i = 2; i <= n / i; i++) // 遍历从2到sqrt(n)的所有整数{if (n % i == 0) // 如果i是n的因子{res = res / i * (i - 1); // 更新结果，使用欧拉函数公式while (n % i == 0) n /= i; // 将n中所有i的因子去除}}if (n > 1) res = res / n * (n - 1); // 如果n大于1，说明n本身是一个质数，更新结果return res; // 返回最终结果
}int main()
{int n;cin >> n; // 读取输入的整数n，表示接下来要处理的数的数量while (n--) // 循环n次{int a;cin >> a; // 读取每个数acout << oula(a) << endl; // 计算并输出a的欧拉函数值}return 0; // 程序结束
}【运行结果】
3
3
2
6
2
8
4