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

      例如， 10= 2*5     φ(10)=10×(1-1/2)×(1-1/5)=4;     这4个数是1, 3, 7, 9 。

         30=2*3*5   φ(30)=30×(1-1/2)×(1-1/3)×(1-1/5)=8;  这8个数是1,7,11,13, 17, 19, 23, 29。

       按欧拉函数的求法，可以编写如下的源程序。

      （3）源程序2。

#include <stdio.h>
int main()
{
      int n,i,ans,t;
      while (scanf("%d", &n) && n!=0)
      {
            ans = n;
            t=n;
            for (i=2;i*i<=t;i++)
                if (t % i == 0)                 // 找到一个质因数i
                 {
                      ans -= ans/i;
                      while (t % i == 0)    // 将质因数i全去掉
                               t /= i;
                 }
            if (t!=1) ans -= ans/t;
            printf("%d\n",ans);
      }
      return 0;
}

      将源程序2提交给 POJ 2407， 可以Accepted。

      将此源程序的printf("%d\n",ans);改写为 printf("%d\n",n-ans-1); 后，提交给 HDU 1787 “GCD Again”，也可以Accepted。

【例2】还是最简真分数。

      输入一个正整数n，求分母在指定区间[2，n]的最简真分数共有多少个？

      例如，输入5，输出应为 9。这9个最简真分数是 {1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5} 。

      （1）编程思路。

      例1的源程序2可以求欧拉函数φ(n)的值。用一个循环求出 φ(2)+φ(3)+…+φ(n)的累加和，即得本题的输出。

      （2）源程序。