|poj 2407|欧拉函数|Relatives

poj传送门 简单的求 φ(n) ，复习了一下模板

#include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #define ms(i,j) memset(i,j, sizeof i); using namespace std; int phi(int n) { int m = sqrt(n+0.5); int ans = n; for (int i=2;i<=m;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 n; while (scanf("%d", &n)==1 && n) { printf("%d\n", phi(n)); } return 0; }