素数判定 (64bit)

2 secs 1024 MB
mizar's icon mizar

解説

まず、エラトステネスの篩で 264=232=4294967296\sqrt{2^{64}}=2^{32}=4294967296 以下の自然数に含まれる 203280221203280221 個の素数を用意し、それを用いて 試し割り法 を用いる方法で間に合うかについて言及します。 1秒間に 10億回 = 10910^9 回 試し割りできるとして (1クエリあたり約0.2秒)、この問題では最大 1000010000 個の整数が与えられるため、これでは実行時間が間に合いません。

手元の環境では、比較的高速な実装をしても 2322^{32} 以下の素数を列挙するためのエラトステネスの篩に 約0.7秒、高速な整除判定用の定数生成に 約1.2秒、2億回の整除判定に 1クエリあたり 約0.2~0.3秒 程度の実行時間、高速な整除判定用の定数を保存するメモリ空間 約3.2GiB 程度 ( 203280221×16203280221 \times 16 bytes ) + α を要しました。(実行時間・メモリ使用量ともに実行制限を超過)

そのため、より高速な素数判定法を用いる必要があります。

また、この問題で与えられる数は 64ビット符号なし整数型 を正しく扱えているか、それが難しい言語でも工夫して実装できているか、をテストの一環に含めているため、問題のクエリごとの制約は 2642^{64} 未満の非負整数としています。

この問題をクリアしたら、64ビット数の素因数分解にも挑戦してみてください。 問題例: Library Checker: Factolize

想定解: Miller-Rabin素数判定法

Writer解: C++ (GCC/Clang)

Writer解: Rust

Writer解: Python

Pythonでは TLE を防ぐため、 input() ではなく sys.stdin などを用いて入力の最適化をした方が良いようです。

Writer解: Ruby

別解: Baillie-PSW素数判定法

  • {2}\lbrace 2 \rbrace の Miller-Rabin素数テストと、 強いリュカ擬素数(strong Lucas pseudoprime)テスト を組み合わせた、 Baillie-PSW素数判定法 という方法もあります。これは、2つの素数テストのいずれでも probably prime (おそらく素数) と判定されてしまう合成数が 2642^{64} 未満の範囲では存在しない事を利用しています。
  • Baillie–PSW primality test, en.wikipedia.org

高速化: モンゴメリ剰余乗算、 Barrett reduction

  • a×bmodna\times b\mod n のような剰余乗算の計算を、 加減算・乗算・シフト演算 を主に使って行う モンゴメリ剰余乗算 を使うと、 C や Rust などの高速な言語においては、低速な剰余算の実行回数を低減させることにより、 Miller-Rabin素数判定法 や Baillie-PSW素数判定法 をより速く計算することができます。Python などの比較的低速な言語においては、低速な剰余算の実行回数を減らせるメリットよりも、代わりに必要となる 加減算・乗算・シフト演算 の演算回数の増加によるデメリットの方が大きくなるため、逆効果になる場合があります。
  • 法が 2322^{32} 未満の範囲では、 Barrett reduction と呼ばれる方法も使われています。 例: C++向けの AtCoder Library における、 dynamic modint の剰余乗算の実装
  • モンゴメリ乗算, ja.wikipedia.org
  • Barrett reduction, en.wikipedia.org

関連問題

関連記事