程序运行后，输出 264.000000。即所有以2010为分母的最简真分数的和是264。

      小朋友是没法像程序一样硬算的。1/2010+7/2010+11/2010+…+2099/2010=264。

      小朋友有小朋友的聪明，1/2010是最简真分数，那么2099/2010 也一定是最简真分数。

      i/2010 是最简真分数，那么 （2010-i）/2010 也一定是最简真分数。

      1/2010 + 2099/2010=1         i/2010 +（2010-i）/2010=1。

      小朋友知道了以2010为分母的最简真分数有528个，因此它们的和为 528/2 = 264。

      因为2010分解质因数后，因数有2、3、5和67四个，用于考察集合的包含与容斥计算量略大但又可以完成，可以算是一道很好的竞赛试题。

     在这道试题的基础上，我们看这样一个问题。

【例1】最简真分数。

      任意输入一个正整数n，求以n为分母的最简真分数有多少个？

     （1）编程思路1。

      将输入的n作为分母，穷举分子i （1≤i≤n-1）。因此，程序可先写成如下的循环：

         for (i=1; i<=n-1; i++)
        {
               对每一分数i/n，进行是否存在公因数的检测。根据检测的结果决定是否计数；
        }
      在上面的循环体中需要对每一分数i/n，进行是否存在公因数的检测。如果分子i与分母n存在大于1的公因数k，说明i/n不是最简真分数，不予计数。怎样进行检测呢？
      因为公因数k的取值范围为[2，i]，因而设置u循环在[2，i]中穷举k，若满足条件
            i%k==0 && n%k==0
      说明分子分母存在公因数k，标记t=1后退出。
      在对因子k进行循环穷举前，可设置标志t=0。退出因子穷举循环后，若t=1，说明分子和分母存在公因子；若保持原t=0，说明分子分母无公因数，统计个数。

      （2）源程序1。

#include <stdio.h>
int main()
{
      int n,i,k,t,cnt;
      while (scanf("%d",&n) && n!=0)
      {
           cnt=0;
           for (i=1;i<=n-1;i++)       // 穷举分子
           {
                t=0;
                for (k=2;k<=i;k++)  // 穷举因数
                    if (i%k==0 && n%k==0)
                    {
                         t=1;
                         break;          // 分子分母有公因数舍去
                    }
               if (t==0)
                     cnt++;           // 统计最简真分数个数
          }
          printf("%d\n",cnt);
      }
      return 0;
}

      将上面的源程序提交给 POJ 2407 “Relatives”，判定为Time Limit Exceeded。  POJ 2407的题意是： 输入正整数N，求小于或等于N ([1,N])，且与N互质的正整数（包括1）的个数。这与求最简真分数的意思完全一致。

      上面源程序1的方法简单直接，但对于N值较大的话，会超时的。因此，我们应找到快速的求法。在数论中，欧拉函数就很好地解决了这样的问题。

      在数论，对于正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名，一般简记为φ函数。 例如，φ(8)=4，因为1,3,5,7均和8互质。