GESP 题解库 / 5 级题解 / [GESP202509 五级] 数字选取 · 第 6 / 23 题
GESP202509 五级 · P14073 · 简单

数字选取

从 1 ~ n 中选尽量多的数,使任意两个互质,求最大个数。

📊
n ≤ 10⁵
数值范围
🔢
int
数值类型
⚡
O(n log log n)
时间复杂度
🎯
质数计数 + 构造
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定正整数 n,现在有 1, 2, …, n 共 n 个整数。请你从中选取一些整数,使得所选取的任意两个不同整数均互质(即最大公因数为 1)。求最多能选多少个。

例:n = 9 时可以选 1, 5, 7, 8, 9 共 5 个。

💡
人话翻译:这题有一个漂亮的结论——答案就是 1 +(1 ~ n 中质数的个数)。因为 1 与任何数互质,而所有质数之间两两互质;并且不可能再多选了,原因是"每个大于 1 的数都要占用一个不同的质因子"。

🔍 关键词提取

互质质数计数上界证明埃氏筛

已知条件

项目说明
输入一个正整数 n
输出最多能选取的整数个数
数据范围1 ≤ n ≤ 10⁵
约束所选集合中任意两个不同的数互质
含 1gcd(1, x) = 1 对任意 x 成立

需要解决的问题

02
思维导图
整理解题思路的全貌
🔢 答案是 1 + 质数个数
💡 构造下界
选 1(与谁都互质)
选所有 ≤ n 的质数
质数之间两两互质
得到 1 + π(n) 个数
🚫 证明上界
设 x 是所选的大于 1 的数
记 p(x) 为它的最小质因子
p(x) ≤ n 且 p(x) 是质数
不同 x 的 p(x) 必不相同
🔍 关键推理
若 p(x) = p(y)
则 p 同时整除 x 和 y
gcd(x,y) ≥ p > 1
与互质矛盾!
📊 计数
所以最多 π(n) 个大于 1 的数
加上 1 共 1 + π(n)
用埃氏筛统计 π(n)
输出答案
03
样例手算推导
样例 n = 6 和 n = 9 的验证

🧮 样例 1:n = 6,答案 4

1 ~ 6 中的质数是 2、3、5,共 3 个。

1
构造一组可行解

选 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 个数

2
能不能选 5 个?

1 ~ 6 中偶数是 2、4、6

任取 5 个数,由抽屉原理必然包含至少 2 个偶数

而任意两个偶数 gcd ≥ 2,不互质

所以不可能选到 5 个

❌ 上限就是 4

1 + 3 = 4 ✓

🧮 样例 2:n = 9,答案 5

1 ~ 9 中的质数是 2、3、5、7,共 4 个。

选取方案元素是否两两互质
质数 + 11, 2, 3, 5, 7✅(4+1 = 5 个)
题面给的方案1, 5, 7, 8, 9✅ 也是 5 个
尝试加合数 41, 2, 3, 5, 7, 4❌ gcd(2,4) = 2
尝试加合数 61, 2, 3, 5, 7, 6❌ gcd(2,6) = 2
尝试加合数 91, 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)"用了一个很巧妙的映射思路。

1
给每个大于 1 的数配一个"标签"

设选出的集合为 S

对 S 中每个 x > 1,取它的最小质因子 p(x)

显然 p(x) 是质数,且 p(x) ≤ x ≤ n

标签是"≤ n 的质数"

2
不同数的标签必须不同

假设 x ≠ y 但 p(x) = p(y) = p

那么 p | x 且 p | y

所以 gcd(x, y) ≥ p > 1

这与"任意两个数互质"矛盾!

✅ 标签互不相同

3
得出结论

所以 S 中大于 1 的元素与"≤ n 的质数"之间是一一对应

个数 ≤ π(n)

再加上元素 1(最多一个)

所以 |S| ≤ 1 + π(n)

✅ 上界得证

⚠️
注意上界证明中的关键点:我们用的是"最小质因子"而不是"任意质因子"——因为只有唯一确定的"最小"才能保证标签是良定义的,从而能建立一一对应。这是数论证明中常用的"构造单射"技巧。
04
解法对比
质数计数 vs 暴力搜索

⚔️ 解法对比

🟢 埃氏筛 + 质数计数(推荐) 推荐

筛出 1 ~ n 的质数,答案 = 1 + 质数个数

  • 时间 O(n log log n)
  • n = 10⁵ 时约 10⁴ 次标记
  • 代码 12 行
  • 有严格的证明支撑
💡
实现:isP[0] = isP[1] = false; 筛完后统计 isP 中为 true 的个数再加 1。注意 n = 1 时答案也是 1(只选 1)。

🟠 回溯搜索

枚举子集或回溯选择,检查互质性

  • 时间指数级
  • n = 30 就已不可行
  • 完全不可行
  • 没有任何优化空间
⚠️
注意:本题 n ≤ 10⁵,搜索类做法根本不可能。而且本题有精确的数学结论,不需要搜索——这类"求最大数量"的题往往有贪心或数论结论。

📈 性能对比

方案复杂度(n = 10⁵)可行性
埃氏筛 + 计数约 10⁴✅ 瞬间完成
回溯搜索指数级❌ 完全不可行
05
算法流程图
筛质数并计数
开始读入 n;isP[1..n] 全部初始化为 trueisP[1] = false(1 不是质数)i 从 2 到 √nisP[i] 为真吗?是 ✓把 i 的所有倍数标记为非质数否 ✗跳过统计 isP[2..n] 中 true 的个数 cnt输出 cnt + 1(加上数字 1)结束i 加 1 继续筛
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔢 最多可选取数量计算器

输入 n,程序会筛出 1 ~ n 的质数并给出最大选取数量。

结果会显示在这里

点按钮开始 →

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

💻 完整 C++ 代码

#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 也要选)
⚠️
两个坑:① 忘记加 1(1 与任何数互质,一定可以选);② 内层从 i 而不是 i * i 开始,虽然结果正确但会慢一些。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

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

输入答案考察点
64题面样例 1
95题面样例 2
11只有 1 可选(1 不是质数,所以答案是 0 + 1 = 1)
22选 1 和 2
33选 1、2、3
105质数有 2、3、5、7 共 4 个 → 4 + 1 = 5
✅
自查清单:① 统计的是质数个数吗?② 最后加 1 了吗?③ n = 1 的边界对吗?

🚨 易错点清单

⚠️
忘记加 1:数字 1 与任何数互质,一定可以选,答案是 π(n) + 1。
⚠️
n = 1 时出错:此时 π(1) = 0,答案应为 1(只选 1)。
⚠️
以为答案与具体选法有关:最优解可能不唯一,但个数是唯一确定的。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n log log n)
空间复杂度
O(n)
n 最大
10⁵
运算量
约 10⁴ ~ 10⁵

时间怎么算的?

空间都用在哪?

一个长度为 n + 1 的布尔数组。

✅ 瞬间完成。关键在于识别出"答案是 1 + π(n)"这个结论,而不是去搜索。

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

🔗 常用技巧小抄

// 埃氏筛标准模板
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)避免无谓的搜索
🌟
思考题:如果题目改成"选出的数中任意两个的gcd 都不超过 1"(即允许相等),答案会变吗?(提示:不会变——因为题目已经要求"两个不同的数",而 gcd(x, x) = x,所以同一个数不能选两次。这类"读清约束条件"的功夫在竞赛中非常重要。)