说明
质数算法常见于RSA中应用这个方法来判定一个数是否是素数。
IMG001.png
代码
package arithmetic
import (
"math"
)
//IsPrimeNumber 检查是否质数
func IsPrimeNumber(num uint64) bool {
if num == 2 || num == 3 {
return true
}
if num%2 == 0 {
return false
}
var sqrt = uint64(math.Sqrt(float64(num)))
var i uint64 = 3
for ; i < sqrt; i += 2 {
if num%i == 0 {
return false
}
}
return true
}
代码说明
算法核心就是将参数开根号，然后不断尝试整除。能够被整除说明不是质数返回false，否则返回true。
优化思路
尽可能减少for循环次数，以提高算法效率。
