Mathematical knowledge: Euler function - Euler function

subject ：AcWing 873. Euler function
Given n A positive integer ai, Please find the Euler function of each number .

The definition of Euler function
1∼N China and N The number of Coprime numbers is called Euler function , Write it down as ϕ(N).
If in the basic theorem of arithmetic ,N=p₁^a1p₂^a2…p_m^am, be ：
ϕ(N) = N×(p₁−1)/p₁×(p₂−1)/p₂×…×(p_m−1)/p_m
Input format
The first line contains integers n.

Next n That's ok , Each line contains a positive integer a_i.

Output format
The output, n That's ok , Each line outputs a positive integer a_i The Euler function of .

Data range
1≤n≤100,
1≤a_i≤2×10⁹

sample input ：

3
3
6
8

sample output ：

2
2
4

#include <iostream>

using namespace std;

int main()
{
    
    int n;
    cin>>n;
    while(n--)
    {
    
        int a;
        cin>>a;
        int res=a;
        for(int i=2;i<=a/i;i++)
            if(a%i==0)
            {
    
                res=res/i*(i-1);
                while(a%i==0)a/=i;
            }
        if(a>1)res=res/a*(a-1);
        cout<<res<<endl;
    }
    return 0;
}