从 1 ~ n 中选尽量多的数,使任意两个互质,求最大个数。
给定正整数 n,现在有 1, 2, …, n 共 n 个整数。请你从中选取一些整数,使得所选取的任意两个不同整数均互质(即最大公因数为 1)。求最多能选多少个。
例:n = 9 时可以选 1, 5, 7, 8, 9 共 5 个。
互质质数计数上界证明埃氏筛
| 项目 | 说明 |
|---|---|
| 输入 | 一个正整数 n |
| 输出 | 最多能选取的整数个数 |
| 数据范围 | 1 ≤ n ≤ 10⁵ |
| 约束 | 所选集合中任意两个不同的数互质 |
| 含 1 | gcd(1, x) = 1 对任意 x 成立 |
1 ~ 6 中的质数是 2、3、5,共 3 个。
选 1、2、3、5
检查两两:gcd(1,2)=1、gcd(1,3)=1、gcd(1,5)=1
gcd(2,3)=1、gcd(2,5)=1、gcd(3,5)=1
全部互质 ✅
✅ 得到 4 个数
1 ~ 6 中偶数是 2、4、6
任取 5 个数,由抽屉原理必然包含至少 2 个偶数
而任意两个偶数 gcd ≥ 2,不互质
所以不可能选到 5 个
❌ 上限就是 4
1 + 3 = 4 ✓
1 ~ 9 中的质数是 2、3、5、7,共 4 个。
| 选取方案 | 元素 | 是否两两互质 |
|---|---|---|
| 质数 + 1 | 1, 2, 3, 5, 7 | ✅(4+1 = 5 个) |
| 题面给的方案 | 1, 5, 7, 8, 9 | ✅ 也是 5 个 |
| 尝试加合数 4 | 1, 2, 3, 5, 7, 4 | ❌ gcd(2,4) = 2 |
| 尝试加合数 6 | 1, 2, 3, 5, 7, 6 | ❌ gcd(2,6) = 2 |
| 尝试加合数 9 | 1, 2, 3, 5, 7, 9 | ❌ gcd(3,9) = 3 |
1, 5, 7, 8, 9——它没有选 2 和 3,所以腾出了位置给 8 和 9(8 只含质因子 2,9 只含质因子 3)。这说明最优解不唯一,但个数是唯一确定的:1 + π(n)。证明"不可能超过 1 + π(n)"用了一个很巧妙的映射思路。
设选出的集合为 S
对 S 中每个 x > 1,取它的最小质因子 p(x)
显然 p(x) 是质数,且 p(x) ≤ x ≤ n
标签是"≤ n 的质数"
假设 x ≠ y 但 p(x) = p(y) = p
那么 p | x 且 p | y
所以 gcd(x, y) ≥ p > 1
这与"任意两个数互质"矛盾!
✅ 标签互不相同
所以 S 中大于 1 的元素与"≤ n 的质数"之间是一一对应
个数 ≤ π(n)
再加上元素 1(最多一个)
所以 |S| ≤ 1 + π(n)
✅ 上界得证
筛出 1 ~ n 的质数,答案 = 1 + 质数个数
isP[0] = isP[1] = false; 筛完后统计 isP 中为 true 的个数再加 1。注意 n = 1 时答案也是 1(只选 1)。枚举子集或回溯选择,检查互质性
| 方案 | 复杂度(n = 10⁵) | 可行性 |
|---|---|---|
| 埃氏筛 + 计数 | 约 10⁴ | ✅ 瞬间完成 |
| 回溯搜索 | 指数级 | ❌ 完全不可行 |
输入 n,程序会筛出 1 ~ n 的质数并给出最大选取数量。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; bool isP[100005]; int main() { int n; scanf("%d", &n); // 埃氏筛 for (int i = 0; i <= n; i++) isP[i] = true; if (n >= 0) isP[0] = false; if (n >= 1) 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; // 从 i*i 开始标记 } } int cnt = 0; for (int i = 2; i <= n; i++) if (isP[i]) cnt++; printf("%d\n", cnt + 1); // 质数个数 + 数字 1 return 0; }
i * i 开始?因为比 i * i 更小的 i 的倍数(如 2i、3i)已经在前面的质数轮次里被标记过了,不必重复。这个优化让埃氏筛的复杂度降到 O(n log log n)。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
isP[0] = isP[1] = false; | 特殊值 | 0 和 1 都不是质数 |
for (j = i * i; j <= n; j += i) | 筛掉倍数 | 从 i² 开始,避免重复标记 |
cnt++ | 统计质数个数 | 得到 π(n) |
printf("%d\n", cnt + 1) | 输出答案 | 别忘了加 1(数字 1 也要选) |
i 而不是 i * i 开始,虽然结果正确但会慢一些。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
6 | 4 | 题面样例 1 |
9 | 5 | 题面样例 2 |
1 | 1 | 只有 1 可选(1 不是质数,所以答案是 0 + 1 = 1) |
2 | 2 | 选 1 和 2 |
3 | 3 | 选 1、2、3 |
10 | 5 | 质数有 2、3、5、7 共 4 个 → 4 + 1 = 5 |
一个长度为 n + 1 的布尔数组。
✅ 瞬间完成。关键在于识别出"答案是 1 + π(n)"这个结论,而不是去搜索。
// 埃氏筛标准模板 bool isP[N]; for (int i = 2; i < N; i++) isP[i] = true; 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; // 线性筛(欧拉筛):每个合数只被最小质因子筛一次,O(n) vector<int> primes; vector<bool> isP(N, true); for (int i = 2; i < N; i++) { if (isP[i]) primes.push_back(i); for (int p : primes) { if ((long long)i * p >= N) break; isP[i * p] = false; if (i % p == 0) break; } } // 结论汇总:从 [1, n] 中选最多互质的数 -> 1 + π(n)
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 埃氏筛 | 标记倍数筛质数 | 所有需要质数表的题目 |
| 单射构造证明 | 给每个元素配唯一标签 | 组合计数、上界证明 |
| 识别数学结论 | 答案 = 1 + π(n) | 避免无谓的搜索 |