寻找整数次幂根 [英] Finding integer power roots

问题描述

什么是最好的（最有效的）算法来找出一些所有整数次幂的根源？

What is the best (most efficient) algorithm for finding all integer power roots of a number?

也就是说，赋予了许多 N ，我想为发现 B （基地）和电子（指数），使得

That is, given a number n, I want to find b (base) and e (exponent) such that

ň= B ^电子

n = b^e

我想获得所有可能的值对 B 和电子

I want to obtain all the possible value pairs of b and e

诗： N B 和电子是是正整数

推荐答案

我觉得暴力方法应该工作：尝试所有电子期从2（1是一个简单的解决方案）及以上，以 R =正^ 1 / E ，一个双。如果研究小于2，停止。否则，计算 CEIL（R）^ E 和楼（R）^ E ，并把它们比作 N （需要 CEIL 和地板来弥补浮点错误再presentations）。假设你的整数适合64位，你就不会需要尝试电子的超过64个值。

I think brute force approach should work: try all es from 2 (1 is a trivial solution) and up, taking r = n ^ 1/e, a double. If r is less than 2, stop. Otherwise, compute ceil(r)^e and floor(r)^e, and compare them to n (you need ceil and floor to compensate for errors in floating point representations). Assuming your integers fit in 64 bits, you would not need to try more than 64 values of e.

下面是在C ++中的一个例子：

Here is an example in 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调用时，它会产生这样的输出：

When invoked with 65536, it produces this output:

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

这篇关于寻找整数次幂根的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！