ProbablyPrimeで素数判定

Golangでの素数判定にはmath/bigのProbablyPrimeが使える。

メソッドのシグネチャは func (x *Int) ProbablyPrime(n int) bool。
このメソッドは疑似ランダムで選ばれたn個の数字を用いてxが(おそらく)素数かどうか判定する。
xが素数なら必ずtrueを返し、xがランダムに選ばれた素数でない数字ならおそらくfalseを返す。
false-positive (素数でないのに誤って素数と判定してしまう)確率は最大で$(\frac{1}{4})^{n}$。

$2^{64}$よりも小さい数字なら返り値は100%正しい。

main.go

package main

import (
	"fmt"
	"math/big"
)

func main() {
	var prime, nonPrime big.Int
	prime.SetString("20988936657440586486151264256610222593863921", 10)
	nonPrime.SetString("20988936657440586486151264256610222593863922", 10)
	fmt.Println(prime.ProbablyPrime(0)) // 素数の場合
	fmt.Println(nonPrime.ProbablyPrime(0)) // 素数じゃない場合
}

実行結果

$ go run main.go
true
false