题目解析 本题若我们直接使用质因数分解，对于 AiA_iAi 执行普通的质因数分解，时间复杂度为 O(⌊Ai⌋)\mathrm{O}(\lfloor\sqrt{A_i}\rfloor)O(⌊Ai ⌋)，对于 NNN 个查询，总的时间复杂度为 O(N⌊max⁡(Ai)⌋)\mathrm{O}(N\lfloor\sqrt{\max(A_i)}\rfloor)O(N⌊max(Ai ) ⌋)；然而这个计算量达到了 104×105=10910^4 \times 10^5 = 10^9104×105=109 级别，无法在时限内通过题目。 根据 素数定理： π(x)≈xln⁡x\pi(x) \approx \frac{x}{\ln{x}} π(x)≈lnxx 其中 π(x)\pi(x)π(x) 表示：不超过 xxx 的整数中素数的数量。 实际上 10510^5105 以内的素数只有 959295929592 个。 所以我们可以把 10510^5105 内所有的 959295929592 个素数预处理，来加速质因数分解，使其复杂度降为 O(π(⌊max⁡(Ai)⌋)\mathrm{O}(\pi(\lfloor\sqrt{\max(A_i)}\rfloor)O(π(⌊max(Ai ) ⌋)。这样整个算法时间复杂度为 O(N×π(⌊max⁡(Ai)⌋))\mathrm{O}\left(N \times \pi(\lfloor\sqrt{\max(A_i)}\rfloor)\right)O(N×π(⌊max(Ai ) ⌋))；其计算量大约为 104×104=10810^4 \times 10^4 = 10^8104×104=108，可以在时限内通过题目。 AC代码

解法：我们从 222 开始，枚举不超过 Ai\sqrt{A_i}Ai 的质因子，然后判断即可。 注意一定得遍历质数，不然单次查询时间复杂度就会退化至 O(Ai)O(\sqrt{A_i})O(Ai )。 时间复杂度：O(Ailn⁡ln⁡Ai+QAiln⁡Ai)O(\sqrt{A_i}\ln\ln A_i+Q\dfrac{\sqrt{A_i}}{\ln A_i})O(Ai lnlnAi +QlnAi Ai )。