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

[「uint64で表現できる素数の最大値」でググって](https://www.google.com/search?q=uint64%E3%81%A7%E8%A1%A8%E7%8F%BE%E3%81%A7%E3%81%8D%E3%82%8B%E7%B4%A0%E6%95%B0%E3%81%AE%E6%9C%80%E5%A4%A7%E5%80%A4)みても、AI に聞いても、ドンピシャ（正しい値）のものがなかったので、自分のググラビリティとして。

## TL; DR <sub><sup>（今北産業）</sup></sub>

> `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`）
1. `2^64-1` より小さく、一番大きい素数は `18,446,744,073,709,551,557`
1. 以下は Go 言語（以下 golang）による算出
    
    ```go: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)
    }
    ```

- [オンラインで動作を見る](https://go.dev/play/p/W0DkdVNagZl) @ Go Playground

:::note info

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

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

```shell-session
$ 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
```

- [オンラインで動作を見る](https://go.dev/play/p/l_m59dtvZrR) @ Go Playground

:::

## TS; DR <sub><sup>（あいつら、みんな嘘つき）</sup></sub>

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

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

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

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

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

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

素数をゴニョゴニョしている中で、ふと「`uint64` で扱える最大の素数は何だろう？」と思い[「uint64で表現できる素数の最大値」でググって](https://www.google.com/search?q=uint64%E3%81%A7%E8%A1%A8%E7%8F%BE%E3%81%A7%E3%81%8D%E3%82%8B%E7%B4%A0%E6%95%B0%E3%81%AE%E6%9C%80%E5%A4%A7%E5%80%A4)みても、ピンとくるものがありませんでした。

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

| ![スクリーンショット 2024-12-26 5.35.10.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/78776/f25a77f1-9574-3ef4-e4a7-78728c165e49.png) |
| :-- |
| 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` と言ってきました。

| ![スクリーンショット 2024-12-22 15.13.42.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/78776/6d8e9a6d-3d1b-4ddf-ca02-40585635805f.png) |
| :-- |
| ほんとだもん！ほんとに ChatGPT がいったんだもん！うそじゃないもん！ |

しかし、[`18446744073709551611` をググって](https://www.google.com/search?q=%2218446744073709551611%22+18%2C446%2C744%2C073%2C709%2C551%2C611)も素数であるという情報がありません。

確認のため、[Dario Alpern](https://www.alpertron.com.ar/EPERS.HTM) 氏の[オンライン素数解析ツール](https://www.alpertron.com.ar/ECM.HTM) で `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 で計算してみることにしました。

```shell-session
$ go run .
The largest prime less than 18446744073709551615 is: 18446744073709551557
```

- [オンラインで計算を見る](https://go.dev/play/p/W0DkdVNagZl) @ GoPlayground

この値（`18,446,744,073,709,551,557`）を[先ほどのツール](https://www.alpertron.com.ar/ECM.HTM)で確認すると、素数であることに間違いないようです。

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

| ![スクリーンショット 2024-12-22 15.29.09.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/78776/214cc8d5-d535-3dfa-462b-4bfe9e51e9b6.png) |
| :--- |
| ChatGPT の後出しジャンケン |

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

| Gemini「手前の聞き方がザルだからでごザルよ。拙者ならこう聞くでごザル。」 |
| :--: |
| ![スクリーンショット 2024-12-27 11.36.20.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/78776/4689c79a-e29d-9098-74ed-39e32c70af40.png) |