說(shuō)明

質(zhì)數(shù)算法常見(jiàn)于RSA中應(yīng)用這個(gè)方法來(lái)判定一個(gè)數(shù)是否是素?cái)?shù)。

IMG001.png

代碼

package arithmetic

import (
    "math"
)

//IsPrimeNumber 檢查是否質(zhì)數(shù)
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
}

代碼說(shuō)明

算法核心就是將參數(shù)開(kāi)根號(hào)，然后不斷嘗試整除。能夠被整除說(shuō)明不是質(zhì)數(shù)返回false，否則返回true。

優(yōu)化思路

盡可能減少for循環(huán)次數(shù)，以提高算法效率。