C++

$\color{#cc33ff}{— > 算法基础课题解}$

欧拉函数：

$1 ∼ N 中与 N 互质的数的个数被称为欧拉函数，记为 ϕ(N)。$

$code:$

时间复杂度：$O(sqrt(n))$

#include <iostream>
#include <algorithm>

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 * (1 - 1 / i);
                res = res / i * (i - 1);
                while (a % i == 0) a /= i;
            }
        if (a > 1) res = res / a * (a - 1);

        cout << res << endl;
    }
    return 0;
}