首先有以下性质：(p 为素数)
1. φ（p）=p-1
2. 如果i mod p==0，那么φ( i*p )=p*φ( i )
3. 若i mod p≠0，那么φ（i*p）=φ（i）*（p-1）
证明见http://blog.csdn.net/Lytning/article/details/24432651，在此表示感谢
典型题目见http://poj.org/problem?id=3090
#include<iostream>// 在筛素数的同时，把欧拉函数求出
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#define M 1000001
using namespace std;
int phi[M],prime[M],tot,ans;
bool notp[M];
void getphi()
{phi[1]=1;for(int i=2;i<=M;i++){if(!notp[i]){prime[++tot]=i;phi[i]=i-1;//i是素数 }for(int j=1;j<=tot&&i*prime[j]<=M;j++){notp[i*prime[j]]=1;//不是素数 if(i%prime[j]==0)// 如果i mod p==0，那么φ( i*p )=p*φ( i ){phi[i*prime[j]]=phi[i]*prime[j];break;//筛素数省时 }// 若i mod p≠0，那么φ（i*p）=φ（i）*（p-1）else phi[i*prime[j]]=phi[i]*(prime[j]-1);}}return;
}
int main()
{getphi();for(int i=1;i<=100;i++){printf("%d %d\n",i,phi[i]);}return 0;
} 
