解説

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

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

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

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

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

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

• $2^{64}$ 未満の範囲においては、 $\lbrace 2, 325, 9375, 28178, 450775, 9780504, 1795265022 \rbrace$ をそれぞれ底とする7回の Miller-Rabin素数テスト を用いる事で、決定的に素数を判定できます。 $2^{32}$ 未満の範囲においては、 $\lbrace 2,7,61 \rbrace$ をそれぞれ底とする3回の Miller-Rabin素数テスト を用いて素数判定できます。 参考: Deterministic variants of the Miller-Rabin primality test, Created and maintained by Wojciech Izykowski.
• また、与えられた数を適切なハッシュ関数で前処理する事で、 Miller-Rabin素数テスト の回数を $2^{32}$ 未満の範囲では $1$ 回、 $2^{64}$ 未満の範囲では (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素数判定法

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

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

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

関連問題

• yukicoder: No.3030 ミラー・ラビン素数判定法のテスト 素数判定 9.93sec 制約: $n\leq 10^4, x_i\lt 2^{63}$
• Library Checker: Primality Test 素数判定 5sec 制約: $Q\leq 10^5, n_i\leq 10^{18}$
• Library Checker: Factolize 素因数分解 10sec 制約: $Q\leq 100, a_i\leq 10^{18}$

関連記事

• 64bit数の素数判定