质数判断算法 Go

说明

质数算法常见于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循环次数，以提高算法效率。