More than 5 years have passed since last update.
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
Register as a new user and use Qiita more conveniently
- You get articles that match your needs
- You can efficiently read back useful information
- You can use dark theme