随机选择一个数，则它出现在答案中的概率至少为 $\frac12$，选择足够多的数后便能大概率求出正确答案。选择一个数后，它的约数最多只有约 $10^5$ 个，求出每个数和它的 $\gcd$，做后缀和便能求出答案。注意到我们并不需要真正分解这个数，只需要找到一组基能够唯一分解所有 $\gcd$ 即可。

时间复杂度 $O(k(n\log a_i+w(a_i)\sigma_0(a_i)))$。其中 $k$ 为所选择的数的个数。