解説
まず、エラトステネスの篩で 264=232=4294967296 以下の自然数に含まれる 203280221 個の素数を用意し、それを用いて 試し割り法 を用いる方法で間に合うかについて言及します。
1秒間に 10億回 = 109 回 試し割りできるとして (1クエリあたり約0.2秒)、この問題では最大 10000 個の整数が与えられるため、これでは実行時間が間に合いません。
手元の環境では、比較的高速な実装をしても 232 以下の素数を列挙するためのエラトステネスの篩に 約0.7秒、高速な整除判定用の定数生成に 約1.2秒、2億回の整除判定に 1クエリあたり 約0.2~0.3秒 程度の実行時間、高速な整除判定用の定数を保存するメモリ空間 約3.2GiB 程度 ( 203280221×16 bytes ) + α を要しました。(実行時間・メモリ使用量ともに実行制限を超過)
そのため、より高速な素数判定法を用いる必要があります。
また、この問題で与えられる数は 64ビット符号なし整数型 を正しく扱えているか、それが難しい言語でも工夫して実装できているか、をテストの一環に含めているため、問題のクエリごとの制約は 264 未満の非負整数としています。
この問題をクリアしたら、64ビット数の素因数分解にも挑戦してみてください。 問題例: Library Checker: Factolize
想定解: Miller-Rabin素数判定法
- 264 未満の範囲においては、 {2,325,9375,28178,450775,9780504,1795265022} をそれぞれ底とする7回の Miller-Rabin素数テスト を用いる事で、決定的に素数を判定できます。 232 未満の範囲においては、 {2,7,61} をそれぞれ底とする3回の Miller-Rabin素数テスト を用いて素数判定できます。 参考: Deterministic variants of the Miller-Rabin primality test, Created and maintained by Wojciech Izykowski.
- また、与えられた数を適切なハッシュ関数で前処理する事で、 Miller-Rabin素数テスト の回数を 232 未満の範囲では 1 回、 264 未満の範囲では (1.6万~26万個の定数と引き換えに) 2~3 回に抑える方法 も知られています。 参考: Forisek, Michal and Jakub Jancina. “Fast Primality Testing for Integers That Fit into a Machine Word.” Conference on Current Trends in Theory and Practice of Informatics (2015).
- ミラー–ラビン素数判定法, ja.wikipedia.org
Writer解: C++ (GCC/Clang)
Writer解: Rust
Writer解: Python
Pythonでは TLE を防ぐため、 input()
ではなく sys.stdin
などを用いて入力の最適化をした方が良いようです。
Writer解: Ruby
別解: Baillie-PSW素数判定法
- 底 {2} の Miller-Rabin素数テストと、 強いリュカ擬素数(strong Lucas pseudoprime)テスト を組み合わせた、 Baillie-PSW素数判定法 という方法もあります。これは、2つの素数テストのいずれでも
probably prime
(おそらく素数) と判定されてしまう合成数が 264 未満の範囲では存在しない事を利用しています。
- Baillie–PSW primality test, en.wikipedia.org
高速化: モンゴメリ剰余乗算、 Barrett reduction
- a×bmodn のような剰余乗算の計算を、 加減算・乗算・シフト演算 を主に使って行う モンゴメリ剰余乗算 を使うと、 C や Rust などの高速な言語においては、低速な剰余算の実行回数を低減させることにより、 Miller-Rabin素数判定法 や Baillie-PSW素数判定法 をより速く計算することができます。Python などの比較的低速な言語においては、低速な剰余算の実行回数を減らせるメリットよりも、代わりに必要となる 加減算・乗算・シフト演算 の演算回数の増加によるデメリットの方が大きくなるため、逆効果になる場合があります。
- 法が 232 未満の範囲では、 Barrett reduction と呼ばれる方法も使われています。 例: C++向けの AtCoder Library における、 dynamic modint の剰余乗算の実装
- モンゴメリ乗算, ja.wikipedia.org
- Barrett reduction, en.wikipedia.org
関連問題
関連記事