我一直得到错误“不能使用a(类型int)作为math.Pow的参数中的类型float64,不能使用x(类型int)作为math.Pow的参数中的类型float64,无效操作:math.Pow(a,x)% n(类型float64和int不匹配)”
func pPrime(n int) bool {
var nm1 int = n - 1
var x int = nm1/2
a := 1;
for a < n {
if (math.Pow(a, x)) % n == nm1 {
return true
}
}
return false
}
5条答案
按热度按时间pvabu6sv1#
以防你不得不重复使用它并保持它更干净一点。
sg2wtvxw2#
如果你的输入是
int
,而输出总是int
,那么你处理的是32位数,编写自己的函数来处理这个乘法比使用math.Pow
更有效。math.Pow
,正如其他答案中提到的,需要64位值。以下是15^15的基准比较(接近32位表示的上限):
结果是:
我认为最好的解决方案是你应该编写类似于上面所示的
IntPow(m, n int)
的函数。我的基准测试显示,与使用math.Pow
相比,它在单个CPU核上的运行速度快4倍以上。nmpmafwu3#
由于没有人提到一个有效的方法(对数)来处理整数
x
和n
,如果你想自己实现它,如下所示:jq6vz3qz4#
如果你想得到整数的精确幂,使用(* big.Int). Exp.你可能很快就会溢出int64,得到大于2的幂。
iqxoj9l95#
虽然Eissa对高效解决方案的上述回答在技术上是正确的,但递归可能会降低性能。请参阅The most efficient way to implement an integer based power function pow(int, int)以获得更优的解决方案。以下是翻译成Go语言的C解决方案:
在我的基准测试中,这几乎是递归版本的两倍。