線形篩を使います。

各 \(i\) (\(1\le i\le M\)) に対して、\(i\) の最小素因数を（全体で）\(O(M)\) 時間で求めることができるデータ構造です。（\(1\) の最小素因数については、文脈に応じて \(1\) としたり \(\infty\) としたりします。）

\(i\) の（重複を含めた）素因数の個数を \(f(i)\)、\(i\) の最小素因数を \(\operatorname{lpf}(i)\) と書くと、

\[ f(i) = \begin{cases} 0, & \text{if } i = 1; \\ f(i/{\operatorname{lpf}(i)}) + 1, & \text{if }i \gt 1 \end{cases} \]

が成り立つので、DP によって各 \(f(i)\) を \(O(M)\) 時間で求めることができます。

よって、（公式解説 の考察を踏まえて）全体で \(O(N+\max_i A_i)\) 時間で解くことができます。

おまけ：線形篩を使って \(\operatorname{lpf}(i)\) のテーブルを作っておくことで、各 \(1\le i\le M\) の約数の個数なども \(O(M)\) 時間で求めることができます。

→ 記事を書きました