线性时间内的完美功率检测
我正在尝试编写一个 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
我的问题是,有没有更有效的方法来找到这些值?我在网上找到了一些文档,但这比我高中代数复杂得多。我怎样才能以更有效的方式实现这一点?
谢谢!
I'm trying to write a C program which, given a positive integer n (> 1) detect whether exists numbers x and r so that n = x^r
This is what I did so far:
while (c>=d) {
double y = pow(sum, 1.0/d);
if (floor(y) == y) {
out = y;
break;
}
d++;
}
In the program above, "c" is the maxium value for the exponent (r) and "d" will start by being equal to 2. Y is the value to be checked and the variable "out" is set to output that value later on. Basically, what the script does, is to check if the square roots of y exists: if not, he tries with the square cube and so on... When he finds it, he store the value of y in "out" so that: y = out^d
My question is, is there any more efficient way to find these values? I found some documentation online, but that's far more complicated than my high-school algebra. How can I implement this in a more efficient way?
Thanks!
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
发布评论
评论(4)
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
在您的评论之一中,您表示您希望它与巨大的数字兼容。在这种情况下,您可能需要引入 GMP 库,它支持任意大数的操作,其中之一检查它是否是完美幂。
它是开源的,因此如果您不想引入整个库,您可以查看源代码并了解他们是如何做到的。
In one of your comments, you state you want this to be compatible with gigantic numbers. In that case, you may want to bring in the GMP library, which supports operations on arbitrarily large numbers, one of those operations being checking if it is a perfect power.
It is open source, so you can check out the source code and see how they do it, if you don't want to bring in the whole library.