1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

ProbablyPrimeで素数判定

Posted at

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

メソッドのシグネチャは 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
1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?