Uint64 で表現できる素数の最大値は 18446744073709551557

「uint64で表現できる素数の最大値」でググってみても、AI に聞いても、ドンピシャ（正しい値）のものがなかったので、自分のググラビリティとして。

TL; DR _{^{（今北産業）}}

Uint64 型で表現できる最大の素数は 18,446,744,073,709,551,557です。これは、uint64 で扱える最大値（2^64 - 1）よりも小さく、一番大きい素数です。

1. 符号なし INT64（UINT64）が扱える最大値は 2^64-1（18,446,744,073,709,551,615）

2. 2^64-1 より小さく、一番大きい素数は 18,446,744,073,709,551,557

3. 以下は Go 言語（以下 golang）による算出

   main.go

   package main
   
   import (
       "fmt"
       "math"
       "math/big"
   )
   
   func main() {
       // uint64の最大値を取得
       maxUint64 := new(big.Int).SetUint64(math.MaxUint64) // =2^64-1 =18446744073709551615
   
       // uint64の最大値より小さく、最大の素数を見つける
       prime := new(big.Int).Set(maxUint64)
       for !isPrime(prime) {
           prime.Sub(prime, big.NewInt(1)) // prime--
       }
   
       fmt.Println("The largest prime less than", maxUint64, "is:", prime)
       // Output:
       // The largest prime less than 18446744073709551615 is: 18446744073709551557
   }
   
   // isPrime は n が素数の場合 true を返す。
   // ProbablyPrime メソッドは n が 2^64 より小さいなら 100% の確率で素数判定できる。
   func isPrime(n *big.Int) bool {
       // 2未満の数値は素数ではない
       if n.Cmp(big.NewInt(2)) < 0 {
           return false
       }
   
       return n.ProbablyPrime(0)
   }
   

• オンラインで動作を見る @ Go Playground

UINT 型で表現できる最大の素数値一覧

• uint8: 251
• uint16: 65,521
• uint32: 4,294,967,291
• uint64: 18,446,744,073,709,551,557

$ go run .
The largest prime less than the max value of uint8 (255) is: 251
The largest prime less than the max value of uint16 (65535) is: 65521
The largest prime less than the max value of uint32 (4294967295) is: 4294967291
The largest prime less than the max value of uint64 (18446744073709551615) is: 18446744073709551557

• オンラインで動作を見る @ Go Playground

TS; DR _{^{（あいつら、みんな嘘つき）}}

golang で、素数を使ってゴニョゴニョしていたら、静的解析ツール（golangci-lint）から「uint --> int の型変換でオーバーフローするリスクあり」的なお叱りを受けました。まれによくある gosec の G115 エラーってやつです。

$ golangci-lint run
totp/example_ecdh_test.go:172:16: G115: integer overflow conversion uint -> int (gosec)
			keyLen = int(outLen)
			            ^

このような場合、「変換前の値が最大値以下であるか」を事前にチェックしておくことでエラーを回避できます。

maxInt16 := uint(32767) // 最大値を決めておく
keyLen := int(maxInt16)

// maxInt16 以下なら変換 & 割り当て。本当は超えていたらエラーにした方が良い。
if outLen < maxInt16 {
    keyLen = int(outLen)
}

さて、今回の俺様プログラムで扱う値は uint64 です。

素数をゴニョゴニョしている中で、ふと「uint64 で扱える最大の素数は何だろう？」と思い「uint64で表現できる素数の最大値」でググってみても、ピンとくるものがありませんでした。

そこで、ググってダメならと Google の噂の双子に聞いてみました。

Gemini「符号なし64bit整数で表現できる素数は 18,446,744,073,709,551,615 です。これは符号なし64bitに格納できる最大の整数です。」

なんか、uint64 の最大値である 18,446,744,073,709,551,615 を素数と言ってきました。

そこで今度は ChatGPT に聞いたら、しれっと 18,446,744,073,709,551,611 と言ってきました。

ほんとだもん！ほんとに ChatGPT がいったんだもん！うそじゃないもん！

しかし、18446744073709551611 をググっても素数であるという情報がありません。

確認のため、Dario Alpern 氏のオンライン素数解析ツール で 18446744073709551615 と 18446744073709551611 を確認してみたところ、やはり素数ではないことがわかりました。

• 18,446,744,073,709,551,615 = 3 × 5 × 17 × 257 × 641 × 65,537 × 6,700,417
• 18,446,744,073,709,551,611 = 11 × 59 × 98,818,999 × 287,630,261

うーん。まぁ、たいした計算量じゃないし、一度わかってしまえば定数として利用できるし、と golang で計算してみることにしました。

$ go run .
The largest prime less than 18446744073709551615 is: 18446744073709551557

• オンラインで計算を見る @ GoPlayground

この値（18,446,744,073,709,551,557）を先ほどのツールで確認すると、素数であることに間違いないようです。

あらためて ChatGPT に聞いてみました。

ChatGPT の後出しジャンケン

「サツキもお父さんも、ChatGPT がうそつきだなんて思っていないよ。謝ってるし。メイはきっとインターネットの森の主に会ったんだ。」（隣のトホホより）

Gemini「手前の聞き方がザルだからでごザルよ。拙者ならこう聞くでごザル。」