翻译。 题解部分 思路： 算法1 暴力枚举。 对于每个 iii 找到其最小质因子 PPP，时间复杂度O(nn)O(n \sqrt{n})O(nn )。 算法2 线性筛。 筛出 [1,109][1,10^{9}][1,109] 的所有素数，对于每个 iii，找到其最小质因子为 PPP 切其相对序列值属于前一部分得到的素数表前 NNN 个数。 时间复杂度 O(nlog⁡n)O(n \log n)O(nlogn)，可以通过此题。 代码 数据较水，直接暴力可以过