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 = out^d

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

谢谢!

Answer 1

在您的一条评论中，您声明您希望它与巨大的数字兼容。在这种情况下，您可能需要引入 GMP library , 它支持对任意大数的操作，其中一个操作是 checking if it is a perfect power .

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