128ビット符号付き整数の最大値は素数 - Rustで任意精度整数演算

概要 2^n-1 型の数はメルセンヌ数と呼ばれ、更に素数である場合にメルセンヌ素数といいます。本記事では、メルセンヌ数に対する高速な素数判定法であるリュカ・レーマーテストを、Rustの任意精度演算用クレート rug を利用して実装します。 実行環境 CPU: Intel Core i7 1.8GHz メモリ: 16GB OS(ホスト): Windows 10 Home 21H1 WSL2: Ubuntu 20.04.3 rustc: Ver. 1.55.0 cargo: Ver. 1.55.0 符号付き整数型の範囲について Rustには組み込みの整数型として 8,\,16,\,32,\,64,\,128 ビット整数[1]がそれぞれ符号付き・符号なしで備わっています[2]。そのうち符号付き整数は、他の多くの言語と同様、2の補数によって負の数が表現されます。したがって、ビット数 n = 8,

[kirakking]

サラッと読めるのにメルセンヌ数に基づいた素数判定の流れが頭に入るすごい力作だった。やっぱり整数論面白いなあ。

[mouki0911]

“128ビット符号付き整数の最大値は素数 ”なんかカッコいい。ひと息で言いたい言葉。

[six13]

結論をズバッと書いている美しい見出し。最後まで読んで見出しに戻るとやはり美しい。

[onesplat]

金とれるでこの記事

[tattyu]

メルセンヌ数の素数じゃない方の擬似素数感がたまらんね。

[yosuke_furukawa]

内容が濃い

[t_mori]

メルセンヌ数

[RySa]

面白そう。後でやってみよ。

[sugyan]

内容の濃さがすごい…