GESP 题解库 / 5 级题解 / [GESP202406 五级] 小杨的幸运数字 · 第 11 / 23 题
GESP202406 五级 · P10720 · 简单

幸运数字

判断每个数是否恰好有两种不同的质因子。

📊
n ≤ 10⁴
数据组数
🔢
值 ≤ 10⁶
数值范围
⚡
O(√x)
单次分解
🎯
质因数分解去重
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

如果一个正整数的质因子恰好有两种不同的,则称为幸运数字。

例:12 = 2 × 2 × 3,质因子是 2 和 3,恰好两种 → 是幸运数字;30 = 2 × 3 × 5 有三种质因子 → 不是。

给定 n 个正整数,逐个判断,是输出 1,不是输出 0。

💡
人话翻译:把每个数做质因数分解,去重后数一数有几种不同的质数,恰好等于 2 就输出 1。注意"不同的质因子"——12 = 2² × 3 里 2 出现两次,但只算一种。

🔍 关键词提取

质因数分解去重计数试除法边界处理

已知条件

项目说明
输入第一行 n;随后 n 行每行一个正整数
输出每行一个 0 或 1
数据范围n ≤ 10⁴
数值范围≤ 10⁶
判定不同质因子个数恰好为 2

需要解决的问题

02
思维导图
整理解题思路的全貌
🔬 分解 + 去重计数
📥 读入
n ≤ 10⁴
每行一个数
值 ≤ 10⁶
逐个独立判断
🔬 试除分解
i 从 2 试到 √x
若 x % i == 0
把 i 除干净并计数 +1
循环结束后若 x > 1 再计一种
✅ 判定
不同质因子个数 == 2
输出 1
否则输出 0
注意 1 的情况
⚠️ 易错点
忘记"除干净"导致重复计数
漏掉最后剩下的 x > 1
忘了质数只有一种因子
分解时改了原数导致后续出错
03
样例手算推导
样例三个数的分解过程

🧮 样例:7、12、30

逐个分解并统计不同的质因子个数。

1
7

i 从 2 试到 √7 ≈ 2.6,即 i = 2

7 % 2 ≠ 0,试除结束

此时 x = 7 > 1 → 再计一种质因子 7

不同质因子:{7},共 1 种

❌ 输出 0

2
12

i = 2:12 % 2 == 0 → 计一种(2),x 除干净变 3

i = 3:3 % 3 == 0 → 计一种(3),x 变 1

x = 1,不再有剩余

不同质因子:{2, 3},共 2 种

✅ 输出 1

3
30

i = 2:30 % 2 == 0 → 计一种(2),x 变 15

i = 3:15 % 3 == 0 → 计一种(3),x 变 5

i = 4:5 % 4 ≠ 0;i = 5 时 5 × 5 > 5,循环结束

x = 5 > 1 → 再计一种(5)

不同质因子:{2, 3, 5},共 3 种

❌ 输出 0

数分解不同质因子个数输出
77{7}10
122² × 3{2, 3}21
302 × 3 × 5{2, 3, 5}30

输出 0、1、0 ✓

🧮 几个边界情形

数分解不同质因子个数输出
1(无质因子)00
2210
42²10
62 × 321
362² × 3²21
2 × 3 × 5 = 30三个质数30
10000002⁶ × 5⁶21
⚠️
两个容易写错的点:① 必须"除干净"——比如 12 里因子 2 出现两次,如果只计数不计次、没除干净,后面还会重复遇到 2,导致重复计数;② 循环结束后若 x > 1,要再计一种——比如 7、30 这种情况,剩下的大质因子在试除范围内找不到,必须单独统计。
04
解法对比
试除法 vs 预处理最小质因子

⚔️ 解法对比

🟢 逐个数试除(推荐) 推荐

对每个数从 2 试除到 √x,统计不同质因子个数

  • 单次 O(√x)
  • x ≤ 10⁶ 时最多试 1000 次
  • n = 10⁴ 时约 10⁷ 次
  • 代码 15 行
💡
量级估算:n ≤ 10⁴、x ≤ 10⁶,每个数试除到 √x ≈ 1000,总共约 10⁷ 次运算,完全可以接受。

🟠 预处理最小质因子表

先筛出 1 ~ 10⁶ 的最小质因子,之后分解 O(log x)

  • 预处理 O(10⁶ log log 10⁶)
  • 每次分解更快
  • 代码多 10 行
  • 本题属于锦上添花
⚠️
什么时候值得:如果 n 很大(比如 10⁶)或数值范围更大,筛法能显著加速。本题直接试除已经够快。

📈 性能对比

方案总运算量(n = 10⁴)代码量
试除法约 10⁷约 15 行
最小质因子筛约 10⁶ + 10⁵约 25 行
05
算法流程图
逐个分解并统计因子种类
开始读入 n处理每个数 xcnt = 0;i 从 2 试到 i × i ≤ xx % i == 0 吗?是 ✓cnt 加 1,把 i 除干净否 ✗i 加 1 继续循环结束后 x 是否大于 1?是 ✓cnt 加 1(剩下一个大质因子)否 ✗不处理输出 cnt == 2 ? 1 : 0结束还有数字 → 继续分解
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔬 幸运数字判定器

每行输入一个正整数,程序会分解质因数并判断是否恰好有两种不同质因子。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);

    while (n--) {
        int x;
        scanf("%d", &x);

        int cnt = 0;                 // 不同的质因子个数
        for (int i = 2; (long long)i * i <= x; i++) {
            if (x % i == 0) {
                cnt++;               // i 是一个新的质因子
                while (x % i == 0) x /= i;   // 把 i 除干净,避免重复计数
            }
        }
        if (x > 1) cnt++;            // 剩下的大质因子

        printf("%d\n", cnt == 2 ? 1 : 0);
    }
    return 0;
}
🔑
为什么"除干净"这么重要?以 12 为例:若只把 i = 2 计数一次但不除干净,那 x 还是 12;下一轮 i 变化后仍可能再次遇到因子 2,导致同一种质因子被计数多次。写成 while (x % i == 0) x /= i; 就能保证每种质因子只被统计一次。

📖 关键几行怎么看

代码作用为什么这样写
i * i <= x试除上界只需试到 √x;注意 x 在变化,所以条件用当前 x
cnt++计数一种质因子每发现一个新因子就加一
while (x % i == 0) x /= i;除干净保证同一质因子只统计一次
if (x > 1) cnt++;处理剩余剩下的是一个大质因子,别忘了计
⚠️
三个坑:① 忘记除干净导致重复计数;② 循环结束后没有 if (x > 1) cnt++;③ 判断写成 cnt >= 2(题目要求恰好两种)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
70只有一种质因子(7)
121题面样例:2² × 3
300三种质因子:2、3、5
10没有质因子,0 种
20质数,只有一种
36136 = 2² × 3²,不同质因子只有 2、3 两种
1000000110⁶ = 2⁶ × 5⁶,两种质因子
✅
自查清单:① 除干净了吗?② 补了剩余因子吗?③ 判断是"恰好等于 2"吗?

🚨 易错点清单

⚠️
没除干净:12 里因子 2 出现两次,若不除干净会被重复计数,把 12 误判为 3 种因子。
⚠️
漏掉剩余大质因子:如 7、30 的最后一个因子在试除范围内找不到,必须用 if (x > 1) cnt++ 补上。
⚠️
判断写成 ≥ 2:题目要求恰好两种。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n √X)
空间复杂度
O(1)
n 最大
10⁴
X 最大
10⁶

时间怎么算的?

空间都用在哪?

只用几个整型变量。

✅ 约千万次运算,C++ 一秒内轻松完成。如果数据范围更大,可改用最小质因子筛法。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 质因数分解(统计不同质因子)的标准模板
int distinctPrimeFactors(int x) {
    int cnt = 0;
    for (int i = 2; (long long)i * i <= x; i++) {
        if (x % i == 0) {
            cnt++;
            while (x % i == 0) x /= i;    // 除干净
        }
    }
    if (x > 1) cnt++;                      // 剩余的大质因子
    return cnt;
}

// 如果要统计"总的质因子个数(含重数)"
// 就把 while 里的 cnt++ 移到循环内
int totalPrimeFactors(int x) {
    int cnt = 0;
    for (int i = 2; (long long)i * i <= x; i++)
        while (x % i == 0) { x /= i; cnt++; }
    if (x > 1) cnt++;
    return cnt;
}

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
质因数分解试除 + 除干净约数、质因子、gcd/lcm 类题目
去重计数同一质因子只算一次所有涉及"不同质因子"的题
剩余大质因子if (x > 1) cnt++分解模板的必备收尾
🌟
思考题:如果题目改成"恰好有 k 种不同质因子",代码要改哪里?(提示:只需把最后的判断从 cnt == 2 改成 cnt == k,其余完全不动。而"恰好 k 个质因子(含重数)"则需要用另一个统计方式——注意区分"不同质因子"和"质因子总个数"这两个概念。)