Go语言的费马小

以下是使用Go语言实现费马小定理的示例代码：

package main

import "fmt"

// 计算 a^b % m 的结果
func modExp(a, b, m int64) int64 {
   
    if m == 1 {
   
        return 0
    }
    result := int64(1)
    base := a % m

    for b > 0 {
   
        if b%2 == 1 {
   
            result = (result * base) % m
        }
        base = (base * base) % m
        b /= 2
    }

    return result
}

// 使用费马小定理判断是否为质数
func isPrime(n int64) bool {
   
    if n <= 1 {
   
        return false
    }
    if n <= 3 {
   
        return true
    }

    // 迭代次数，也是费马小定理的参数
    k := 5
    for i := 0; i < k; i++ {
   
        // 生成一个随机的 a，范围在[2, n-1]之间
        a := 2 + (int64(i) % (n - 3))
        if modExp(a, n-1, n) != 1 {
   
            return false
        }
    }

    return true
}

func main() {
   
    // 调用费马小定理判断一个数字是否为质数
    fmt.Println(isPrime(17)) // true
    fmt.Println(isPrime(21)) // false
}

在上面的示例中，modExp函数用于计算 a^b % m，isPrime函数用于使用费马小定理判断一个数字是否为质数。程序输出结果中，17是质数，21不是质数。