while(scanf("%d",&n),n != 0){
        if(n == 1){
            printf("0\n");  continue;
        }
        ans = n;
        for(int i = 2;i*i <= n;++i){
            if( n % i == 0 ){
                ans = ans - ans/i;
                while(n%i == 0){
                    n /= i;
                }
            }
        }
        // n is prime itself
        if(n != 1)  ans = ans - ans / n;
        printf("%d\n",ans);
    }

• 真的很帅，请路过的大牛能解释下其中的原理，先谢了！ (136) nothing828 2010-03-13 14:09:28
  • Re:真的很帅，请路过的大牛能解释下其中的原理，先谢了！ (180) Desertangle 2010-05-26 22:26:32
    • Re:真的很帅，请路过的大牛能解释下其中的原理，先谢了！ (51) jimoqianchen 2010-08-19 12:37:51
      • 欧拉函数.... (41) fgwe12 2012-03-25 18:47:17
  • Re:真的很帅，请路过的大牛能解释下其中的原理，先谢了！ (162) 19880901 2011-04-01 18:30:25
• 帅～ (479) btw616 2010-08-04 04:58:16
• 其实是把分解质因子的代码和求欧拉函数值的代码结合起来，省了一点而已，没什么好稀奇的 (0) dalugun 2011-07-29 15:58:21
  • Re:其实是把分解质因子的代码和求欧拉函数值的代码结合起来，省了一点而已，没什么好稀奇的 (0) 771385494 2012-04-23 22:27:22