2

有名な紙PRIMES is in Pを勉強して混乱してください。

提案されたアルゴリズムの最初のステップは次のとおりです。アルゴリズムIf (n=a^b for nature number a and b>1), output COMPOSITE.全体が多項式時間で実行されるため、このステップもO（（log n）^ c）で完了する必要があります（入力サイズがO（log n）の場合）。ただし、理解できません。グーグルした後にターゲットをヒットするアルゴリズム。

質問：

多項式時間で他の数の指数であるかどうかをテストするために利用できるアルゴリズムはありますか？

よろしくお願いします！

4

3 に答える 3

4

n=a^b(a > 1 の場合) b ≤ log 2 n の場合、これをテストするためにすべてbの より小さいかどうかを確認できます。2 から log n までlog nの検索を繰り返すことができ、検索のために 1..平方根(n)。しかし、バイナリ検索の反復には O( ) の時間がかかります。最後に、検索の各ステップ (チェックのために見つかったもの) で、 a b == nかどうかを確認する必要があり、これには O(log n) かかるため、合計検索時間は O になります。 (ログ3 n)。もっと速い方法があるかもしれませんが、AKSが O(log 6 n) であることを知っていれば、この O(log 3 n) は何の害もありません。balogna

于 2012-04-18T18:27:42.163 に答える
2

b^e = n となる b と e が存在する場合、数 n は完全べき乗です。たとえば、216 = 6^3 = 2^3 * 3^3 は完全累乗ですが、72 = 2^3 * 3^2 はそうではありません。数値が完全べき乗であるかどうかを判断する秘訣は、数値が完全べき乗である場合、指数 e が log2 n 未満でなければならないことを知ることです。さらに、素数 e をテストすることだけが必要です。数値が複合指数の完全ベキである場合、複合コンポーネントの素因数の完全ベキにもなるためです。たとえば、2^15 = 32768 = 32^3 = 8^5 は完全立方根であり、完全 5 乗根でもあります。したがって、アルゴリズムは、log2 n 未満の素数のリストを作成し、それぞれをテストすることです。log2 n は小さく、素数のリストはさらに小さいため、n が大きい場合でも、これは大した作業ではありません。

ここで実装を見ることができます。

于 2012-04-18T18:23:11.920 に答える
1 
public boolean isPerfectPower(int a) {
    if(a == 1) return true;
    for(int i = 2; i <= (int)Math.sqrt(a); i++){
        double pow = Math.log10(a)/Math.log10(i);
        if(pow == Math.floor(pow) && pow > 1) return true;
    }
    return false;
}
于 2016-04-21T18:48:33.343 に答える