C12第1章欧拉函数 ϕ(n)

admin

小于等于  n 的所有数中与  n 互质的数的个数。
求单个数的欧拉函数

[C++] 纯文本查看 复制代码

#include <iostream>
using namespace std;

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

    return 0;
}