問題概要
$N \ $個の整数$ \ a_1,a_2,\ldots,a_N \ $が与えられる。
各$ \ a_i \ $について、$a_i \times k \ $が素数となる最小の正整数$ \ k \ $を求めよ。
ただし、そのような$ \ k \ $が存在しないならばNAを出力せよ。
制約
- $1 \leq N \leq 10^6$
- $1 \leq a_i \leq 6 \times 10^6$
解説
各$ \ a_i \ $に対する答えは、$a_i \ $が素数である場合は$ \ 1 \ $。$a_i \ $が$ \ 1 \ $である場合は$ \ 2 \ $。素数でも$ \ 1 \ $でもない場合はNAとなります。 ただし、通常の素数判定法では$ \ a_i \ $が素数かどうか判定するのに$ \ O(\sqrt{a_i}) \ $かかってしまいます。エラトステネスの篩を用いて$ \ O(1) \ $で判定しましょう。
よってこの問題は、$max_a \ $を$ \ \max({a_1,a_2,\ldots,a_N}) \ $としたとき、計算量$ \ O(N + max_a \log \log max_a) \ $で解くことができます。
