\(M=\max(A)\) とします．\(B(=\sqrt M)\)以下の素数については個数の累積和を計算しておきます．

\(B\) より大きい素数については，各 \(i\) について高々 \(1\) つしかないので，Mo’s algorithm を適用します．

全体の計算量は \(\mathrm{O}(N \pi(\sqrt M) + (N+Q)\sqrt {N+Q})\) です．