欧拉函数K

欧拉函数是积性函数——若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 = 1, i;
    for(i = 2; i * i <= n; i++)
    {
        if(n % i == 0)
        {
            n /= i;
            ret *= i-1;
        }
        while(n % i == 0)
        {
            n /= i;
            ret *= i;
        }
    }
    if(n > 1) //如果n是质数的情况下
        ret *= n-1;
    return ret;
}
int main()
{
    int n;
    while(scanf("%d", &n), n)
    {
        printf("%d
", eular(n));
    }
    return 0;
}