将此源程序提交给 POJ 2478 “Farey Sequence”，被判定为Time Limit Exceeded。POJ 2478的题意是：求1~n的欧拉函数的和。

      因为，例1中是在 O(sqrt(n)) 的时间内求出一个数n的欧拉函数值。

      如果要求100000以内所有正整数的欧拉函数值，上面程序采用的方法的复杂度将高达O(N*sqrt(N))。因此，容易超时。

      下面我们寻求更快的求欧拉函数值的方法。

      我们知道，欧拉函数值  φ(n)=n*(1-1/p1)*(1-1/p2)....*(1-1/pk)，其中p1、p2…pk为n的所有质因子。即欧拉函数的值与其质因子有关。用筛法可以方便地求出n以内的所有质数。关于筛法及应用可以参阅本博客中的随笔 POJ中和质数相关的三个例题（POJ 2262、POJ 2739、POJ 3006）。

      那么我们能不能在筛法求质数的同时求出所有数的欧拉函数呢？可以采用如下的方法：

      用筛法一边筛出N以内的所有质数，一边以类似于筛法的思想用质数筛出每个数的欧拉函数φ值。

      这里，利用了欧拉函数的几个基本性质：

      ① 若N是质数p的k次幂，φ(N)=p^k-p^(k-1)=(p-1)p^(k-1)，因为除了p的倍数外，其他数都跟N互质。 
      ② 当N是质数时，φ(N) = N-1。显然，因为N是质数，1~N-1均与N互质。 
      ③ 欧拉函数是积性函数——若m,n互质，φ(m*n)=φ(m)*φ(n) 。

      ④ 假设质数p能整除n，那么

          如果p还能整除n / p ,  φ(n)  = φ(n / p) * p;
          如果p不能整除n / p,   φ(n)  = φ(n / p) * (p - 1)。

      定义数组phi[N]，元素phi[i]表示正整数i的欧拉函数值φ(i)。

      定义数组vis[N]，元素vis[i]=True表示i在筛子中，vis[i]=false表示i不在筛子中，已被筛掉。初始时，vis数组的元素全置为true，表示全部放在筛子中。

     定义数组prime[N]，元素prime[i]的值为第i个质数。

      下面以求20以内所有质数及所有数的φ值为例，来描述筛法的使用。

      1） 从i=2开始循环， vis[2]==true，找到第一个质数2，prime[0]=2，质数个数PNum=1；同时，phi[2]=2-1=1。

      采用循环 for (j = 0; j < pNum && prime[j]*i <MAXN; j++ ) 将筛子中2的各质数倍数筛掉，同时求得相应数的欧拉函数值。（注意这里与通常的筛法有改变，主要为了用质数筛出各数的欧拉函数值）。

      筛去 2*prime[0]=2*2=4，即 vis[4]=false； phi[4]=phi[2]*prime[0]=1*2=2；

      2）i++，进行下次循环， vis[3]==true，找到第2个质数，prime[1]=3，pNum=2，同时phi[3]=3-1=2。

     筛去 3*prime[0]=3*2=6 ，即vis[6]=false;  置phi[6]=phi[3]*(prime[0]-1)=2*1=2；

     筛去 3*prime[1]=3*3=9 ，即vis[9]=false;  置phi[9]=phi[3]*(prime[1])=2*3=6；

     3）i++，进行下次循环， vis[4]==false，4不是质数。

     筛去 4*prime[0]=4*2=8 ，即vis[8]=false;  置phi[8]=phi[4]*(prime[0])=2*2=4；

     筛去 4*prime[1]=4*3=12 ，即vis[12]=false;  置phi[12]=phi[4]*(prime[1]-1)=2*2=4； 

          与  φ(12)=12*(1-1/2)(1-1/3)=4   比较下 更容易理解。

         phi[12]=phi[4]*(prime[1]-1)=phi[2]*prime[0]*(prime[1]-1)=2*(1-1/2)*2*3*(1-1/3)。
      4）i++，进行下次循环， vis[5]==true，找到第3个质数，prime[2]=5，pNum=3，同时phi[5]=5-1=4。

     筛去 5*prime[0]=5*2=10 ，即vis[10]=false;  置phi[10]=phi[5]*(prime[0]-1)=4*1=4；

     筛去 5*prime[1]=5*3=15 ，即vis[15]=false;  置phi[15]=phi[5]*(prime[1]-1)=4*2=8；

     筛去 5*prime[2]=5*5=25 ，即vis[25]=false;   当然我们以20为例的话，25已超出，循环不会执行到。

      同理，6不是质数，筛去 6*2=12，置 phi[12]=phi[6]*(prime[0])= 2*2=4。