ProbablyPrimeを使ってgolangで素数判定

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

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

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

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