题解区满了，再加上这玩意儿也没啥发题解的必要性，就放这儿了。诸君权当作图一乐。

若 $\omega(n)\ge 3$ 则暴力 $O(\sqrt[3]{n})$ 分解要么就直接解决，要么可以归约到 $\omega(n)\le 2$ 的情况。具体是以下三种：

• $n\in {\mathbb P}$，此时答案为 $k$
• $n=pq$，此时答案为 $k^2$
• $n=p^2$，此时答案为 $\binom {k+1} {2}$

仔细想想，第一种可以直接 Miller-Rabin 判掉；第三种也简单。剩下的就是第二种。所以你就做完了。