欧拉函数的施用

欧拉函数的应用
欧拉函数的一些应用。
已知n，求1~n中某个数与n没有大于1的公约数的总个数。欧拉函数的推导略过。这里告诉一些技巧就行。
定义欧拉函数为D（n），定义n=72，D（72）=D（2^3*3^2）=(2-1)2^(3-1)×(3-1)3^(2-1)=24。其中的2和3是n的素数约数，而且必须是素数。欧拉函数的具体代码如下：
int eular(int n)
{
        int ret=1,i;
        for (i=2;i*i<=n;i++){
                if (n%i==0) {
                    n=n/i;
                    ret=ret*(i-1);
                    while (n%i==0){
                        n=n/i;
                        ret=ret*i;
                    }
                }
        }
        if (n>1)
                ret=ret*(n-1);
        return ret;
}
其中的ret就是要求的答案。