欧拉函数
陈子骏
2018-10-10 08:51:30
```
#include<bits/stdc++.h>
const int MAXN=1000010;
int dp[MAXN];
int main(){
memset(dp,0,sizeof(dp));
dp[1]=1;
for(int i=2;i<MAXN;i++){
if(dp[i])continue;
for(int j=i;j<MAXN;j+=i){
if(!dp[j])dp[j]=j;
dp[j]=dp[j]/i*(i-1);
}
}
int N;
while(~scanf("%d",&N))printf("%d\n",dp[N]);
return 0;
}
```