定义：    对于正整数n，φ(n)是小于或等于n的正整数中，与n互质（互质意思为两者公约数只有一个1）的数的数目；

                例如: φ(8) = 4, 因为1，3，5，7均和8互质。

性质：  1.    若p是质数，φ（p）= p-1.

        2.    若n是质数p的k次幂，φ（n）= （p-1）p^(k-1)

n=p*p*p*p...(共K个P)，P是质数，P不能被再次分解成更小的数，因此n只能被这么拆分，因此只能与p的倍数互质，这样的数可以表示成t*p,其中t=1,2,3....pk-1-1，即共有pk-1-1个与n互质，因此φ（n）=φ（p^k）=p^k-1-(pk-1-1)=(p-1）p^(k-1)

        3.    欧拉函数是积性函数，若m，n互质，φ（mn）= φ(m)φ(n)

        根据这3条性质我们就可以退出一个整数的欧拉函数的公式，因为一个数总可以一些质数的乘积的形式,

公式：

φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有不重复的因数，x是不为0的整数。

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

//Accepted 164K 0MS C++ 472B

int work(int n) {

    int rea = n;

    for(int i = 2; i*i<=n; i++) {

        if(n%i == 0) {//I可以是因数

            rea = rea - rea/i;///取x(1-1/p1)=x-x/p1

            while(n%i==0) { n /= i; }//i的N次方有可能也是n的因数

        }

    }

    if(n>1) { rea = rea - rea/n ;}  //防止除完还有一个因数，比如42，除以2得到21，再除以3，得到7，然后i不会再遍历到7，因为7大于根号42。因此最后一步还要处理一下

    return rea;

}

int main()

{

    int n;

    while(scanf("%d", &n) && n) {

        int res = work(n);

        printf("%d\n", res);

    }

    return 0;

}

math2407_Euler's function