欧拉函数的应用，素数定理；

看了DISCUSS中那段超短的代码后才明白欧拉函数直接解决，我之前想的是集合中的容斥定理，实际上这里欧拉公式也实质上就是容斥定理；

另外用了刚学的优化的筛法计算素数表。

# include 
     
      # define N 1000005int m;char pt[N];int p[N/10];void build_ptable(void);int solve(int n);int main(){    int n;        build_ptable();    while (~scanf("%d", &n) && n)        printf("%d\n", solve(n));        return 0;}void build_ptable(void){    int i, j, k;        m = 0;    for (i = 2; i < N; ++i)    {        if (!pt[i]) p[m++] = i;        for (j = 0; j
      
       1; ++i)        if (n%p[i] == 0)         {            ret = ret - ret/p[i];            while (n%p[i] == 0) n /= p[i];        }    if (ret == n) return (n==1 ? 0:n-1);            return ret;}