小杨的幸运数字 题解

一、题目分析

小杨定义“幸运数字”为：恰好包含两种不同质因子 的正整数。例如 $12 = 2^2 \times 3$，质因子集合为 $\{2, 3\}$，共两种，是幸运数字；而 $30 = 2 \times 3 \times 5$，质因子集合为 $\{2, 3, 5\}$，共三种，不是幸运数字。

题目给定 $n$ 个正整数，要求对每个数判断是否为幸运数字，是则输出 $1$，否则输出 $0$。

数据范围：$1 \le n \le 10^4$，单个数值 $2 \le a_i \le 10^6$。

二、解题思路

核心任务是对一个数，统计它不同质因子的个数，然后判断是否等于 $2$。

统计不同质因子个数的常用方法是试除法（分解质因数）：

1. 用 $i$ 从 $2$ 开始遍历，如果 $i \times i \le$ 当前数，检查 $i$ 是否能整除当前数。
2. 若能整除，说明 $i$ 是一个新的质因子，计数加一，然后不断将当前数除以 $i$，直到不能整除为止（这样就把该质因子的所有幂次都除尽，避免重复计数）。
3. $i$ 变大，继续上述操作。
4. 循环结束后，若当前数仍然大于 $1$，说明它本身是一个大于 $\sqrt{\text{原数}}$ 的质因子，计数再加一。

最后，若计数恰好为 $2$，则是幸运数字；否则不是。

三、算法说明

以 $a = 12$ 为例：

• 初始 cnt = 0，当前数 x = 12。
• i = 2，2 * 2 <= 12，12 % 2 == 0，cnt 变为 $1$，然后 x 不断除以 $2$，得到 x = 3。
• i = 3，3 * 3 <= 12（注意上限仍用原数），3 % 3 == 0，cnt 变为 $2$，x 除以 $3$ 得 $1$。
• i = 4，4 * 4 <= 12 成立，但 x = 1，内层 while 不执行。
• i = 5，5 * 5 > 12，循环结束。
• 最后 x = 1，不大于 $1$，不额外计数。
• cnt == 2 → 是幸运数字。

同理，$a = 30$：会得到质因子 $2,3,5$，cnt = 3，不是幸运数字；$a = 7$：循环直接跳过（$2\times 2>7$），最后 x = 7 > 1，cnt = 1，不是幸运数字。

四、时间复杂度分析

对于每个正整数 $a$，试除的循环上限是 $\sqrt{a}$。当 $a \le 10^6$ 时，最多会检查约 $1000$ 个 $i$。结合 $n \le 10^4$，总的检查次数约为 $10^7$ 级别，在 $1000$ms 时间限制内完全可以运行完毕。

空间上仅需存储几个变量，满足 $512$MB 内存限制绰绰有余。

五、参考代码

题目给出了 C++ 参考代码，我们逐段进行解释。

cpp
复制
1#include <bits/stdc++.h>
2using namespace std;
3
4int lucky(int sum) {  // sum 是待判断的数
5    int ans = 0;      // 质因子种类计数
6    int a = sum;      // 保留原数，用作循环上限
7    for (int i = 2; i * i <= a; i++) {
8        if (sum % i == 0) {   // i 是一个质因子
9            ans++;
10            while (sum % i == 0) {
11                sum /= i;     // 除尽该因子
12            }
13        }
14    }
15    if (sum > 1) {    // 剩下的部分是一个大于 sqrt(a) 的质因子
16        ans++;
17    }
18    if (ans == 2) {
19        return 1;
20    } else {
21        return 0;
22    }
23}
24
25int main() {
26    int n;
27    cin >> n;
28    int a;
29    while (n--) {
30        scanf("%d", &a);
31        cout << lucky(a) << endl;
32    }
33    return 0;
34}

代码说明

lucky 函数：

• 形参名为 sum，进入函数后先拷贝一份到 a，保留原始数值。
• ans 用于记录不同质因子个数。
• for 循环从 2 开始，循环条件 i * i <= a。这里使用 a（原数）而非当前 sum，是为了保证即使 sum 在过程中变小，循环上限也不会提前缩小，从而确保所有可能的小于等于 $\sqrt{\text{原数}}$ 的因子都能被检测到。虽然这会多做几次无用的除法（例如当 sum 已经变成 $1$ 后，循环仍可能继续到 i * i > a），但不会影响正确性，且不会超时。
• 当 sum % i == 0 时，i 一定是质因子（因为之前所有比 i 小的因子已经被除尽），ans 加一。
• 内部的 while (sum % i == 0) sum /= i; 负责将该质因子的所有幂次全部除去，保证不会重复计数。
• 循环结束后，若 sum > 1，说明原始的 a 包含一个大于 $\sqrt{a}$ 的质因子，且未被除尽，ans 再加一。
• 最后判断 ans == 2，若相等返回 $1$，否则返回 $0$。

主函数：

• 读入 $n$，循环 $n$ 次，每次读入一个正整数 a，调用 lucky(a) 并输出结果，每行一个。

补充优化（选读）

• 循环条件可以改为 i * i <= sum，这样效率更高，且不影响正确性：当 sum 不断变小，一旦 i * i > sum 就可以提前结束，剩下的 sum 要么是 $1$ 要么是一个质因子。这样可以避免一些多余的检查。
• 对于本题规模，原代码已经足够快，无需额外优化。

六、常见错误与避坑

• 忘记去重：若没有 while 循环彻底除尽同一质因子，会对 $12=2^2 \times 3$ 中的 $2$ 计数两次，导致结果错误。
• 遗漏大质因子：循环结束后忘记判断 sum > 1，会使像 $7$ 这样的质数由于没有执行到 if(sum%i==0) 分支而使得 ans = 0，导致判断出错。
• 循环条件用错：写成 i * i <= sum 并在除的过程中 sum 减小，若使用原始代码中的 a 作为上限没有问题；但如果已经改为 i*i <= sum，则需要注意 sum 变化后循环提前结束，这样做其实更合理，但千万不要混写导致边界错误。

七、总结

本题考察了分解质因数并统计不同质因子个数的基本方法，以及循环边界的细节处理。只要正确实现试除过程，就能轻松通过所有测试数据。对于 $10^6$ 以内的数据，直接试除法完全足够，不需要使用筛法等复杂预处理。