Shogo's Blog

Nov 6, 2025 - 4 minute read - go golang

マイナンバーを全列挙して含まれる素数の数を数えた

背景・目的

「マイナンバー.csvというファイルにチェックディジットの正しい12桁整数を大量に入れておくいたずらを考えた」という𝕏の発言を見て、

そういえば、過去にマイナンバーの可能性のある数列をすべて列挙した人がいたよなーと思い出しました。 完全に二番煎じですが、自分でもやってみました。

前例

マイナンバー一覧生成

C++よくわからずコンパイル通らなかったので、Goで再実装してみました。

package main

import (
  "bufio"
  "io"
  "os"
)

func main() {
  w := bufio.NewWriterSize(os.Stdout, 1<<20)
  for i := range 100_000_000_000 {
    if err := checkDigit(w, i); err != nil {
      panic(err)
    }
  }
  if err := w.Flush(); err != nil {
    panic(err)
  }
}

func checkDigit(w io.Writer, num int) error {
  var buf [13]byte
  a := num % 10
  num /= 10
  b := num % 10
  num /= 10
  c := num % 10
  num /= 10
  d := num % 10
  num /= 10
  e := num % 10
  num /= 10
  f := num % 10
  num /= 10
  g := num % 10
  num /= 10
  h := num % 10
  num /= 10
  i := num % 10
  num /= 10
  j := num % 10
  num /= 10
  k := num % 10
  num /= 10

  if num != 0 {
    panic("num is larger than 11 digits")
  }
  sum := a*2 + b*3 + c*4 + d*5 + e*6 + f*7 + g*2 + h*3 + i*4 + j*5 + k*6
  sum %= 11
  if sum <= 1 {
    sum = 0
  } else {
    sum = 11 - sum
  }
  buf[0] = byte('0' + k)
  buf[1] = byte('0' + j)
  buf[2] = byte('0' + i)
  buf[3] = byte('0' + h)
  buf[4] = byte('0' + g)
  buf[5] = byte('0' + f)
  buf[6] = byte('0' + e)
  buf[7] = byte('0' + d)
  buf[8] = byte('0' + c)
  buf[9] = byte('0' + b)
  buf[10] = byte('0' + a)
  buf[11] = byte('0' + sum)
  buf[12] = '\n'
  _, err := w.Write(buf[:])
  return err
}

ごちゃごちゃとしていて申し訳ない・・・。 for ループ使ったり、Sprintf, Printf 使えばもうちょっとシンプルにかけるだろっていう話はあるんだけど、 チェックデジット生成の処理が軽すぎて、簡単な整形処理がボトルネックになってしまうのです。 結果、愚直に書くのが一番早いという結論になりました。

ではやっていきましょう。 残念ながら手元に1TB保存できるようなストレージはなかったので、列挙と並列してzstdで圧縮します。

% go run main.go | zstd -11 -T0 -v -o out.txt.zstd
*** Zstandard CLI (64-bit) v1.5.7, by Yann Collet ***
Note: 10 physical core(s) detected
/*stdin*\            :  3.62%   (  1.18 TiB =>   43.9 GiB, out.txt.zstd)

結果は43.9GiB。圧縮済みであればUSBメモリーにも十分収まるサイズですね。

SHA256ハッシュを計算してみます。

time zstdcat out.txt.zstd | sha256sum
21077f2dac68161eff9fa39578b55712a5cc315fd7cc89fb415a07d52193074a  -
zstdcat out.txt.zstd  1426.85s user 180.50s system 112% cpu 23:47.51 total
sha256sum  598.59s user 76.96s system 47% cpu 23:47.51 total

先人と同じ結果が得られました。内容はあっていそうです。

素数の数を数えてみる

自分のマイナンバーが素数であるか否か、というのは誰しもが気になるところだと思います。 せっかくマイナンバーの一覧を手に入れたので、その中に含まれる素数の数を数えてみましょう。

$10^6$程度の小さな素数であれば単純なエラトステネスの篩で簡単に求められます。

package main

import "fmt"

var isPrime [1_000_000]bool

func main() {
  for i := 2; i < len(isPrime); i++ {
    isPrime[i] = true
  }

  for i := 2; i*i < len(isPrime); i++ {
    if isPrime[i] {
      for j := i * i; j < len(isPrime); j += i {
        isPrime[j] = false
      }
    }
  }

  for i, p := range isPrime {
    if p {
      fmt.Printf("%d\n", i)
    }
  }
}

しかし、今必要なのは $10^{12}$ までの素数です。 単純に篩にかけるだけではメモリーが足りなくなります。 そこで、区間篩を用いて10億件ごとに分割して素数一覧を計算する方法をとりました。

package main

import (
  "bufio"
  "errors"
  "fmt"
  "io"
  "os"
)

// 10⁶ までの素数を事前計算しておく
var primes = []int{
  2,
  3,
  5,
  7,
  /* ... (snip) ... */
  999983,
}

var primeMap [1_000_000_000]bool
var lower = -1
var upper = -1

func isPrime(num int) bool {
  if num < 2 {
    return false
  }
  // 計算済みの場合は、その結果を返す
  if lower <= num && num <= upper {
    return primeMap[num-lower]
  }

  // 次の10億件についてあらかじめ篩にかけておく
  lower = (num / len(primeMap)) * len(primeMap)
  upper = lower + len(primeMap) - 1
  for i := range primeMap {
    primeMap[i] = true
  }
  for _, prime := range primes {
    if prime*prime > upper {
      break
    }
    for i := upper / prime * prime; i >= lower && i > prime; i -= prime {
      primeMap[i-lower] = false
    }
  }
  return primeMap[num-lower]
}

func main() {
  // 入出力をバッファリングする
  w := bufio.NewWriter(os.Stdout)
  r := bufio.NewReader(os.Stdin)

  for {
    // 標準入力からマイナンバーをひとつ読み込む
    var num int
    if _, err := fmt.Fscanf(r, "%d\n", &num); err != nil {
      if errors.Is(err, io.EOF) {
        break
      }
      panic(err)
    }

    // 素数だったら標準出力へ出力
    if isPrime(num) {
      if _, err := fmt.Fprintf(w, "%012d\n", num); err != nil {
        panic(err)
      }
    }
  }

  if err := w.Flush(); err != nil {
    panic(err)
  }
}

実行結果：

% time zstdcat out.txt.zstd | go run ./is_prime | zstd -11 -T0 -v -o primes.txt.zstd
*** Zstandard CLI (64-bit) v1.5.7, by Yann Collet ***
Note: 10 physical core(s) detected
/*stdin*\            : 24.71%   (  41.4 GiB =>   10.2 GiB, primes.txt.zstd)
zstdcat out.txt.zstd  1423.88s user 620.84s system 4% cpu 11:41:34.52 total
go run ./is_prime  41508.48s user 511.37s system 99% cpu 11:41:34.54 total

% zstdcat primes.txt.zstd | wc -l
 3418925855

34億1892万5855個。

マイナンバーは1000億通りあるので、 仮にランダムにマイナンバーが割り当てられているとすると、3.418925855%の確率で素数、ということになります。

他の人が計算した概算約3%という結果とも一致するので、あってる気がします、たぶん。

まとめ

マイナンバーとして解釈したときにチェックデジットが正しく、素数である12桁の数字は34億1892万5855通り。

🐰 新しいポストが到着しました、
素数を数える知恵の旅、
12桁の数たちが踊り、
ふるいにかけられて輝く、
マイナンバーの謎、解き明かされます ✨

by CodeRabbit

参考