欧拉函数

给定 n 个正整数 ai，请你求出每个数的欧拉函数。欧拉函数的定义1∼N中与 N 互质的数的个数被称为欧拉函数，记为 ϕ(N)。
若在算数基本定理中，N=pa11pa22…pamm，则：
ϕ(N) = N×p1−1p1×p2−1p2×…×pm−1pm
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个正整数 ai。
输出格式
输出共 n 行，每行输出一个正整数 ai 的欧拉函数。
数据范围
1≤n≤100,1≤ai≤2×109
输入样例：
3
3
6
8

输出样例：
2
2
4
欧拉函数其实就是1~N与N互质的数的个数
只要找的一个不与N互质的数,就将它从N里删干净。

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++){
        int a;
        cin >> a;
        int res = a;
        for(int j = 2; j <= a / j; j ++){
            if(a % j == 0){
                while(a % j == 0) a /= j;
                res = res / j * (j - 1);
            }
        }
        if(a > 1) res = res / a * (a - 1);
        cout << res << endl;
    }
    return 0;
}