判断每个数是否恰好有两种不同的质因子。
如果一个正整数的质因子恰好有两种不同的,则称为幸运数字。
例:12 = 2 × 2 × 3,质因子是 2 和 3,恰好两种 → 是幸运数字;30 = 2 × 3 × 5 有三种质因子 → 不是。
给定 n 个正整数,逐个判断,是输出 1,不是输出 0。
12 = 2² × 3 里 2 出现两次,但只算一种。质因数分解去重计数试除法边界处理
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n;随后 n 行每行一个正整数 |
| 输出 | 每行一个 0 或 1 |
| 数据范围 | n ≤ 10⁴ |
| 数值范围 | ≤ 10⁶ |
| 判定 | 不同质因子个数恰好为 2 |
逐个分解并统计不同的质因子个数。
i 从 2 试到 √7 ≈ 2.6,即 i = 2
7 % 2 ≠ 0,试除结束
此时 x = 7 > 1 → 再计一种质因子 7
不同质因子:{7},共 1 种
❌ 输出 0
i = 2:12 % 2 == 0 → 计一种(2),x 除干净变 3
i = 3:3 % 3 == 0 → 计一种(3),x 变 1
x = 1,不再有剩余
不同质因子:{2, 3},共 2 种
✅ 输出 1
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
| 数 | 分解 | 不同质因子 | 个数 | 输出 |
|---|---|---|---|---|
| 7 | 7 | {7} | 1 | 0 |
| 12 | 2² × 3 | {2, 3} | 2 | 1 |
| 30 | 2 × 3 × 5 | {2, 3, 5} | 3 | 0 |
输出 0、1、0 ✓
| 数 | 分解 | 不同质因子个数 | 输出 |
|---|---|---|---|
| 1 | (无质因子) | 0 | 0 |
| 2 | 2 | 1 | 0 |
| 4 | 2² | 1 | 0 |
| 6 | 2 × 3 | 2 | 1 |
| 36 | 2² × 3² | 2 | 1 |
| 2 × 3 × 5 = 30 | 三个质数 | 3 | 0 |
| 1000000 | 2⁶ × 5⁶ | 2 | 1 |
对每个数从 2 试除到 √x,统计不同质因子个数
先筛出 1 ~ 10⁶ 的最小质因子,之后分解 O(log x)
| 方案 | 总运算量(n = 10⁴) | 代码量 |
|---|---|---|
| 试除法 | 约 10⁷ | 约 15 行 |
| 最小质因子筛 | 约 10⁶ + 10⁵ | 约 25 行 |
每行输入一个正整数,程序会分解质因数并判断是否恰好有两种不同质因子。
点按钮开始 →
#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; }
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(题目要求恰好两种)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
7 | 0 | 只有一种质因子(7) |
12 | 1 | 题面样例:2² × 3 |
30 | 0 | 三种质因子:2、3、5 |
1 | 0 | 没有质因子,0 种 |
2 | 0 | 质数,只有一种 |
36 | 1 | 36 = 2² × 3²,不同质因子只有 2、3 两种 |
1000000 | 1 | 10⁶ = 2⁶ × 5⁶,两种质因子 |
if (x > 1) cnt++ 补上。只用几个整型变量。
✅ 约千万次运算,C++ 一秒内轻松完成。如果数据范围更大,可改用最小质因子筛法。
// 质因数分解(统计不同质因子)的标准模板 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++ | 分解模板的必备收尾 |
cnt == 2 改成 cnt == k,其余完全不动。而"恰好 k 个质因子(含重数)"则需要用另一个统计方式——注意区分"不同质因子"和"质因子总个数"这两个概念。)