欧拉函数

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;
}