時間計算量 \(\mathrm{O}(N + M + \max A_i)\) の解法の概略です。まず線形篩と呼ばれる方法で、各数について最小素因数を求めます。次にそれを用いた動的計画法により、\(A_i\) のいずれかと共通の素因数をもつ数を特定します。

実装例 (C++)