c - 线性时间内完美的功率检测

Question

我正在尝试编写一个 C 程序，给定一个正整数 n (> 1) 检测是否存在数字 x 和 r 以便 n = x^r

这是我到目前为止所做的：

while (c>=d) {
    double y = pow(sum, 1.0/d);
    if (floor(y) == y) {
        out = y;
        break;
    }

    d++;
}

在上面的程序中，“c”是指数 (r) 的最大值，“d”将从等于 2 开始。Y 是要检查的值，变量“out”设置为稍后输出该值在。基本上，脚本所做的是检查 y 的平方根是否存在：如果不存在，他会尝试使用平方根，依此类推......当他找到它时，他将 y 的值存储在“out”中，这样: y = 出^d

我的问题是，有没有更有效的方法来找到这些值？我在网上找到了一些文档，但这比我的高中代数要复杂得多。我怎样才能以更有效的方式实现这一点？

谢谢！

score 3 · Accepted Answer

在您的一条评论中，您声明您希望这与巨大的数字兼容。在这种情况下，您可能需要引入GMP 库，它支持对任意大数的操作，其中一项操作是检查它是否是完美的幂。

它是开源的，所以如果你不想引入整个库，你可以查看源代码并看看他们是如何做到的。

score 2 · Accepted Answer

如果n适合固定大小（例如 32 位）的整数变量，则最佳解决方案可能只是对此类数字的列表进行硬编码并对其进行二进制搜索。请记住，在int范围内，大致有

在 32 位中，大约是 65536 + 2048 + 256 + 128 + 64 + ... < 70000。

score 0 · Accepted Answer

您需要 r-base logarithm，使用身份使用自然对数计算它

所以：

log_r(x) = log(x)/log(r)

所以你需要计算：

x = log(n)/log(r)

（在我的脖子上，这是高中数学。这立即解释了我必须查找我是否正确记住了那个身份:)）

score 0 · Accepted Answer

在计算 y 之后

double y = pow(sum, 1.0/d);

您可以获得最接近它的 int，您可以使用自己的幂函数来检查 sum 的相等条件。

int x = (int)(y+0.5);
int a = your_power_func(x,d);
if (a == sum)
     break;

我想这样你可以确认一个数字是否是其他数字的整数幂。

4 回答 4