欧拉函数是积性函数——若m,n互质，φ(mn)=φ(m)φ(n)。
特殊性质：当n为奇数时，φ(2n)=φ(n),
φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),
其中p1,p2,p3,p4,……pn为x的所有质因数，
原因：如果x = p^k,那么p的所有倍数与x都不互质，所以除了p的倍数外的数的个数就是x*(1-1/p)个
比如下面的题目：
Description
Given n, a positive integer, how many positive integers less than n are relatively prime to n? Two integers a and b are relatively prime if there are no integers x > 1, y > 0, z > 0 such that a = xy and b = xz.
Input
There are several test cases. For each test case, standard input contains a line with n <= 1,000,000,000. A line containing 0 follows the last case.
Output
For each test case there should be single line of output answering the question posed above.
Sample Input
7
12
0
Sample Output
6
4 题目要求：输入若干个数n，输入以0,0结束
找出比n小的数中与a互质的数的个数 用欧拉定理，任意一个数可以分解成小于等于它的质数的乘积，
如果n是质数: 那么比他小的数中和它互质的数的个数为n-1
如果n不是质数：n = p1^a1 * p2^a2 * p3^a3 * p4^a4 * …… *pn^an;
那么n的欧拉函数值就等于pi^ai（1<=i<=n）的欧拉函数的积
每一项的欧拉函数就等于pi^ai * （1-1/pi）化简后就是(pi-1)*pi^(n-1) 原来的解题思路一直超时，当时是按照常规方法来做，把，本来案例个数就很多很多，每个案例中的n还是10e9这么大的，一个一个找素数多麻烦，多浪费时间
欧拉函数就行了啊，欧拉好伟大，赞一个，如果我先学欧拉函数的话肯定不喜欢欧拉，整这么多东西，真难记，可是现在觉得方便多啦…… source
上代码：
#include <stdio.h>
using namespace std;
int eular(int n)
{
int ret = , i;
for(i = ; i * i <= n; i++)
{
if(n % i == )
{
n /= i;
ret *= i-;
}
while(n % i == )
{
n /= i;
ret *= i;
}
}
if(n > ) //如果n是质数的情况下
ret *= n-;
return ret;
}
int main()
{
int n;
while(scanf("%d", &n), n)
{
printf("%d\n", eular(n));
}
return ;
}