统计不超过 n 且最大质因子不超过 B 的正整数个数。
若一个正整数的最大质因子不超过 B,则称它为 B-smooth 数。
给定 n 和 B,求不超过 n 的 B-smooth 数有多少个。
B-smooth质因子埃氏筛反向标记
| 项目 | 说明 |
|---|---|
| 输入 | 两个正整数 n、B |
| 输出 | 不超过 n 的 B-smooth 数的个数 |
| 数据范围 | 1 ≤ n, B ≤ 10⁶ |
| 定义 | 最大质因子 ≤ B |
| 特例 | 1 是 B-smooth 数(没有质因子) |
p, 2p, 3p, … 都标记为不合格先筛出 ≤ 10 的质数,再对 > 3 的质数标记倍数。
2, 3, 5, 7
质数:2、3、5、7
5, 10 被标记为不合格
20 超出范围不管
不合格:5、10
7 被标记为不合格
14 超出范围
不合格:5、7、10
| 数 | 质因数分解 | 最大质因子 | ≤ B = 3? | 合格 |
|---|---|---|---|---|
| 1 | (无) | — | ✅(空真) | 是 |
| 2 | 2 | 2 | ✅ | 是 |
| 3 | 3 | 3 | ✅ | 是 |
| 4 | 2² | 2 | ✅ | 是 |
| 5 | 5 | 5 | ❌ | 否 |
| 6 | 2 × 3 | 3 | ✅ | 是 |
| 7 | 7 | 7 | ❌ | 否 |
| 8 | 2³ | 2 | ✅ | 是 |
| 9 | 3² | 3 | ✅ | 是 |
| 10 | 2 × 5 | 5 | ❌ | 否 |
合格的有 1、2、3、4、6、8、9 共 7 个 ✓
| 情形 | 结果 | 原因 |
|---|---|---|
| B ≥ n | 答案 = n | 所有 ≤ n 的数的质因子都 ≤ n ≤ B |
| B = 1 | 答案 = 1 | 只有 1 合格(2 的最小质因子是 2 > 1) |
| n = 1 | 答案 = 1 | 只有 1 |
| n = 10, B = 10 | 答案 = 10 | 全部合格 |
筛出质数,把 > B 的质数的倍数标为不合格,统计剩余
逐个求最大质因子,判断是否 ≤ B
| 方案 | 运算量(n = 10⁶) | 可行性 |
|---|---|---|
| 反向标记 | 约 3 × 10⁶ | ✅ 稳过 |
| 逐个分解 | 约 10⁹ | ❌ 可能超时 |
输入 n 和 B,程序会标记不合格的数并统计 B-smooth 数。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; const int MAXN = 1000005; bool isP[MAXN]; // 是否为质数 bool bad[MAXN]; // 是否不合格(含有 > B 的质因子) int main() { int n, B; scanf("%d %d", &n, &B); // 埃氏筛:找出 1 ~ n 的所有质数 for (int i = 0; i <= n; i++) isP[i] = true; isP[0] = isP[1] = false; for (int i = 2; (long long)i * i <= n; i++) if (isP[i]) for (int j = i * i; j <= n; j += i) isP[j] = false; // 对每个大于 B 的质数,标记它的所有倍数 for (int p = 2; p <= n; p++) { if (isP[p] && p > B) { for (int m = p; m <= n; m += p) bad[m] = true; } } // 统计合格(含 1) int ans = 0; for (int i = 1; i <= n; i++) if (!bad[i]) ans++; printf("%d\n", ans); return 0; }
m = p 开始(而不是 p * p)?因为在这里我们要标记 p 本身——p > B 说明 p 的最大质因子是 p,本身就不合格。这与"埃氏筛标记合数"不同(那里 p 本身是质数,所以从 p² 开始)。两处起点不同,务必分清。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
isP[0] = isP[1] = false | 筛法特殊值 | 0 和 1 不是质数 |
if (isP[p] && p > B) | 筛选条件 | 只处理"大于 B 的质数" |
for (m = p; m <= n; m += p) | 标记倍数 | 从 p 开始(p 本身也不合格) |
for (i = 1; i <= n; i++) if (!bad[i]) ans++ | 统计 | 从 1 开始,让 1 被计入 |
p * p 开始(漏掉 p 本身);③ 用逐个分解代替筛法(可能超时)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
10 3 | 7 | 题面样例:{1,2,3,4,6,8,9} |
1 1 | 1 | 只有 1 |
5 1 | 1 | B = 1 时只有 1 合格 |
20 2 | 5 | 2-smooth 数:1、2、4、8、16 |
10 10 | 10 | B ≥ n 时全部合格 |
100 5 | 运行验证 | 更大的规模 |
for (m = p; ...),因为 p 本身(> B)也不合格。两个长度为 n + 1 的布尔数组。
✅ 约几百万次操作,瞬间完成。相比逐个分解的 10⁹,快了三个数量级。
// 反向标记模板:从"满足定义"转化为"排除不合格" for (int p = 2; p <= n; p++) if (isP[p] && p > B) for (int m = p; m <= n; m += p) bad[m] = true; // 另一种写法:直接求每个数的最大质因子(线性筛) int mpf[N]; // 最大质因子 for (int i = 2; i <= n; i++) { if (!mpf[i]) { // i 是质数 for (int j = i; j <= n; j += i) mpf[j] = i; } } // 然后 mpf[i] <= B 即为 B-smooth // C++17 求质因数分解(配合试除) // 用 __gcd、__builtin_popcount 等内置函数提高效率 // 复杂度速记 // 埃氏筛:O(n log log n) // Σ_{p <= n} n/p ≈ n ln ln n // 逐个试除分解:O(n√n)
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 反向标记 | 改判为"排除不合格" | 含"最大/最小质因子"约束的计数题 |
| 筛法批量处理 | 调和级数复杂度 | 所有涉及"倍数的性质"的统计 |
| 1 的特殊性 | 没有质因子,空真成立 | 所有质因子相关定义都要留意 |