1

私はオイラーのTotient関数のバージョンを動作させることができましたが、小さい数値で動作するものはあります(ここでは、計算に必要な1024ビット数値と比較して小さいです)

私のバージョンはここにあります -

public static BigInteger eulerTotientBigInt(BigInteger calculate) { 

    BigInteger count = new BigInteger("0");
    for(BigInteger i = new BigInteger("1"); i.compareTo(calculate) < 0; i = i.add(BigInteger.ONE)) { 
        BigInteger check = GCD(calculate,i);

        if(check.compareTo(BigInteger.ONE)==0)  {//coprime
            count = count.add(BigInteger.ONE);          
        }
    }
    return count;
}

これは小さい数値に対しては機能しますが、1 から計算中の数値まで可能な限りすべて反復することによって機能します。大きな BigInteger では、これはまったく実行不可能です。

各反復で数を分割することが可能であり、それらを1つずつ処理する必要がなくなることを読みました。何を何で割るべきかわかりません (私が見た例のいくつかは C であり、long と平方根を使用しています - 私の知る限り、正確な正確な計算はできませんBigInteger の平方根また、このような剰余算術の場合、mod が何であるかを示す引数を関数に含める必要があるかどうかも疑問に思っています。

ここで誰かが私を正しい方向に向けることができますか?

PS Euler Totient Function の変更を見つけたときに、この質問を削除しました。BigIntegers で動作するように調整しました -

public static BigInteger etfBig(BigInteger n) {

    BigInteger result = n;
    BigInteger i;

    for(i = new BigInteger("2"); (i.multiply(i)).compareTo(n) <= 0; i = i.add(BigInteger.ONE)) {
         if((n.mod(i)).compareTo(BigInteger.ZERO) == 0) 
         result = result.divide(i);
         while(n.mod(i).compareTo(BigInteger.ZERO)== 0 ) 
             n = n.divide(i);
     }      
 if(n.compareTo(BigInteger.ONE) > 0)
 result = result.subtract((result.divide(n)));
 return result;
}

そして、正確な結果が得られます.1024ビットの数値を渡すと、ビットは永遠に実行されます（終了したかどうかはまだわかりません.20分間実行されています）。

4

3 に答える 3

10

n の素因数分解を必要とする totient 関数の式があります。ここを見てください。

式は次のとおりです。

phi(n) = n * (p1 - 1) / p1 * (p2 - 1) / p2 ....
were p1, p2, etc. are all the prime divisors of n.

除算は常に正確であるため、浮動小数点ではなく BigInteger のみが必要であることに注意してください。

したがって、問題はすべての素因数を見つけることになり、反復よりも優れています。

ソリューション全体は次のとおりです。

int n;  //this is the number you want to find the totient of
int tot = n; //this will be the totient at the end of the sample
for (int p = 2; p*p <= n; p++)
{
    if (n%p==0)
    {
        tot /= p;
        tot *= (p-1);
        while ( n % p == 0 ) 
            n /= p;
    }
}
if ( n > 1 ) { // now n is the largest prime divisor
    tot /= n;
    tot *= (n-1);
}
于 2012-11-04T07:28:37.880 に答える
1

あなたが書き込もうとしているアルゴリズムは、引数を因数分解することと同等nです。つまり、コンピュータが死ぬか死ぬまで、実際にはそれが永遠に実行されることを期待する必要があります。詳細については、mathoverflowのこの投稿を参照してください。オイラーのトーティエント関数を計算するのはどれくらい難しいですか？。

一方、因数分解された多数のトーティエントの値が必要な場合は、引数を（素数、指数）ペアのシーケンスとして渡します。

于 2012-11-05T01:40:10.987 に答える