7是质数，置prime[3]=7,pNum=4, phi[7]=6。    

                                    筛去 7*2=14，置 phi[14]=phi[7]*(prime[0]-1)= 6*1=6。

          …… 

      （3）采用筛法思想的源程序。

#include <stdio.h>
#include <string.h>
#define MAXN 1000005
int prime[MAXN], pNum, phi[MAXN];
__int64 num[MAXN]={0};
bool vis[MAXN];
int main()
{
      int n,i,j;
      memset(vis,true,sizeof(vis));
      // 下面程序段既求MAXN以内的素数又求欧拉数。
      pNum=0;
      phi[1] = 1;
      for (i = 2; i < MAXN; i++)
      {
             if (vis[i])   //  i是素数
             {  
                   prime[pNum++] = i;
                   phi[i] = i-1;
             }
             for (j = 0; j < pNum && prime[j]*i <MAXN; j++ )
             {
                     vis[prime[j]*i] = false;
                     if (i % prime[j] == 0)
                     {
                           phi[i*prime[j]] = phi[i] * prime[j];
                           break;
                     }
                     else
                           phi[i*prime[j]] = phi[i] *(prime[j] - 1);
             }
       }
      for (i=2;i<MAXN;i++)
      {
            num[i]=num[i-1]+phi[i];
      }
      while (scanf("%d", &n) && n!=0)
      {
            printf("%I64d\n",num[n]);
      }
      return 0;
}

      将用筛法思想改写的源程序提交给 POJ 2478， 可以Accepted。

      将上面的程序略作改动，可以顺便通过 HDU 2824 “The Euler function”。

    （4）进一步讨论。

     上面采用筛法求欧拉函数的值时，我用了3个数组，用于表示数是否在筛子中的标记数组vis，用于保存质数的数组prime，用于保存欧拉函数值的数组phi。虽然看起来直观，好像体现了欧拉函数值与分解质因数相关的概念，但有点繁琐。能否只用一个数组phi，即保存欧拉函数的值，又表示筛子，当然在筛子中的最小数一定是质数，从而又表示了质数呢？

       定义数组phi[N]，初始值全为0，Phi[i]=0表示i在筛子中，i是质数。

      前面介绍过欧拉函数值得标准求法。 

      设正整数N分解质因数后，N=P1^q1*P2^q2*...*Pn^qn.

       则   φ(N)=N*(1-1/P1)*(1-1/P2)*...*(1-1/Pn)。

       显然，若p1是n的质因数，phi[n]一定会作 n*(p1-1)/p1这样的运算。

       下面我以n=30为例介绍phi数组既保存欧拉函数值有当筛子用的方法。