用BigInteger求欧拉函数

本来想搬砖,无奈没砖可搬,DIY 吧,反正也花不了多长事件

 

BigInteger求欧拉函数:

public static BigInteger bigIntegerEuler(BigInteger n) {
        BigInteger ret = new BigInteger(n.toString());

        BigInteger i = new BigInteger("2");
        BigInteger one = new BigInteger("1");
        BigInteger zero = new BigInteger("0");
        for (; i.multiply(i).compareTo(n) <= 0; i.add(one)) {
            if (n.mod(i).compareTo(zero) == 0) {
                ret = ret.subtract(n.divide(i));
                do {
                    n = n.divide(i);
                }while (n.mod(i).compareTo(zero) == 0);
            }
        }

        if (n.compareTo(one) > 0) {
            ret = ret.subtract(ret.divide(n));
        }

        return ret;
    }

 

 

 

参照代码:

ll euler(ll n)  // ll 为 long long
{  
    ll ret=n;  
    for(ll i=2;i*i<=n;i++){  
        if(n%i==0){  
            ret-=ret/i;  
            while(n%i==0){  
                n/=i;  
            }  
        }  
    }  
    if(n>1)ret-=ret/n;  
    return ret;  
}

 

生活依然苦涩.........................

 

上一篇:java大数四则运算


下一篇:裴波那契数列多种解法及数据溢出处理