#include<iostream>
using namespace std;
//φ(n)=n⋅∏ (1-1/pi) O(sqrt(a))

int f_euler(int a) {
	int ans = a;
	int n = a;
	for (int i = 2; i*i <= n; i++) {
		if (n % i == 0) {
			ans = ans / i * (i - 1);
		}
		while (n % i == 0) {
			n /= i;
		}
	}
	if (n > 1) {
		ans = ans / n * (n - 1);
	}

	return ans;
}
int main() {
	int a;
	cin >> a;
	cout<<f_euler(a)<<endl;
	return 0;
}

分解质因数

从数学角度证明：为什么每次得到的 i 都是质因数

核心证明

关键观察

在进入每次循环时，n 已经被之前所有更小的质因子除尽了。

数学证明

定理：如果在第 i 次循环时 n % i == 0，那么 i 一定是质数。

反证法证明：

假设 i 是合数，则 i 可以分解为 i = p × q，其中 p 和 q 都是大于 1 且小于 i 的整数。

因为 n % i == 0，所以 i 整除 n，即 i | n。

由于 p | i 且 i | n，根据传递性，p | n。

矛盾来了：p < i，且 p 是 n 的因子。

但是！由于程序从 2 开始遍历，在到达 i 之前，所有小于 i 的质因子 p 都已经被处理过了。

当处理 p 时，代码执行了： 

while (n % p == 0) {
    n /= p;
}

这会把 n 中所有的 p 因子全部除尽。

所以到第 i 次循环时，n 中已经不含有任何小于 i 的因子 p了。

既然 p | n 且 p < i，这与"n 不含有小于 i 的因子"矛盾！

因此假设不成立，i 不可能是合数，只能是质数。