寻找整数幂根

Question

查找数字的所有整数幂根的最佳(最有效)算法是什么？

也就是说,给定一个数字 n,我想找到 b(基数)和e(指数)这样的

n = b ^e

我想获得的所有可能的值对b和e

Ps:n b并且e是正整数.

Answer 1

首先找到主要因子分解n:n = p1e1 p2e2 p3e3 ...

然后找到最大公约数g的,,使用,... 欧几里德算法.e1e2e3

现在对于任何因素e的g,你可以使用:

b = p1e1/e p2e2/e p3e3/e ...

你有.n = be

Answer 2

我认为蛮力方法应该有效：尝试e从 2 （1 是一个简单的解决方案）开始的所有 s 以及向上，取r = n ^ 1/e, a double。如果r小于2，则停止。否则，计算ceil(r)^e和floor(r)^e，并将它们与n（您需要ceil和floor来补偿浮点表示中的错误）。假设您的整数适合 64 位，您不需要尝试超过 64 个值e。

下面是一个 C++ 示例：

#include <iostream>
#include <string>
#include <sstream>
#include <math.h>
typedef long long i64;
using namespace std;
int main(int argc, const char* argv[]) {
    if (argc == 0) return 0;
    stringstream ss(argv[1]);
    i64 n;
    ss >> n;
    cout << n << ", " << 1 << endl;
    for (int e = 2 ; ; e++) {
        double r = pow(n, 1.0 / e);
        if (r < 1.9) break;
        i64 c = ceil(r);
        i64 f = floor(r);
        i64 p1 = 1, p2 = 1;
        for (int i = 0 ; i != e ; i++, p1 *= c, p2 *= f);
        if (p1 == n) {
            cout << c << ", " << e << endl;
        } else if (p2 == n) {
            cout << f << ", " << e << endl;
        }
    }
    return 0;
}

当使用 65536 调用时，它会产生以下输出：

65536, 1
256, 2
16, 4
4, 8
2, 16