【GESP】C++五级真题（数论、贪心考点） luogu-P14073 [GESP202509 五级] 数字选取
GESP C++ 2025年9月五级真题，数论、贪心考点，题目难度⭐⭐★☆☆，五级来说难度相对简单。洛谷难度等级普及−
luogu-P14073 [GESP202509 五级] 数字选取
题目要求
题目描述
给定正整数 $n$，现在有 $1,2,\ldots,n$ 共计 $n$ 个整数。你需要从这 $n$ 个整数中选取一些整数，使得所选取的整数中任意两个不同的整数均互质（也就是说，这两个整数的最大公因数为 $1$）。请你最大化所选取整数的数量。
例如，当 $n=9$ 时，可以选择 $1,5,7,8,9$ 共计 $5$ 个整数。可以验证不存在数量更多的选取整数的方案。
输入格式
一行，一个正整数 $n$，表示给定的正整数。
输出格式
一行，一个正整数，表示所选取整数的最大数量。
输入输出样例 #1
输入 #1
1
6
输出 #1
1
4
输入输出样例 #2
输入 #2
1
9
输出 #2
1
5
说明/提示
对于 $40\%$ 的测试点，保证 $1\le n\le 1000$。
对于所有测试点，保证 $1\le n\le 10^5$。
题目分析
这道题主要考察数论中的互质概念以及贪心策略。
核心思想
题目要求在 $1$ 到 $n$ 中选取尽可能多的整数，使得任意两个整数互质（最大公因数为 1）。
一、关于 1 的特性：
$1$ 和任何正整数的最大公因数都是 $1$。因此，为了最大化数量，我们一定选取 1。
二、关于大于 1 的数：
对于两个大于 $1$ 的整数 $a$ 和 $b$，如果它们互质，意味着它们不能有共同的质因数。换句话说，如果我们选出的集合中包含 $k$ 个大于 $1$ 的整数，那么这 $k$ 个整数每一个至少包含一个质因数，且这些质因数必须两两不同（否则就会有公因数）。
为了让选出的数最多，我们希望每个数“消耗”的质因数尽可能少。每个大于 $1$ 的数至少有一个质因数。消耗最少的情况就是每个数本身就是一个质数（只包含一个质因数）。
如果我们选取一个合数（例如 $6 = 2 \times 3$），它占用了 $2$ 和 $3$ 两个质因数的“位置”。如果我们选了 $6$，就不能选 $2$、3$、4$、8$、9$ 等等。显然，不如直接选取质数 $2$ 和 $3$ 更划算（选了 $2$ 和 $3$ 只是不能选它们的倍数，但我们获得了 $2$ 个数，而选 $6$ 只有 $1$ 个数）。
贪心策略
综上所述，最优的选取方案是：
- 选取数字 1。
- 选取 $2$ 到 $n$ 之间的所有素数（质数）。
最终答案即为：$n$ 以内素数的个数 + 1。
算法选择
根据 $n$ 的范围（$1 \le n \le 10^5$），我们需要一种高效的方法来统计素数个数。
- 试除法：对每个数判断是否为素数。单次判断 $O(\sqrt{n})$，总复杂度 $O(n\sqrt{n})$。对于 $n=10^5$ 勉强可过，但不是最优。
- 埃氏筛 (Sieve of Eratosthenes)：时间复杂度 $O(n \log \log n)$，效率较高，适合本题。
- 线性筛 (Euler Sieve)：时间复杂度 $O(n)$，效率最高，适合更大范围的数据。
本题数据范围 $10^5$，三种方法均可通过。
示例代码
方法一，试除法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
// 判断一个数是否为素数
// 使用试除法，从 2 遍历到 sqrt(num)
bool isPrime(int num) {
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) {
return false; // 如果能被整除，说明不是素数
}
}
return true; // 无法被整除，说明是素数
}
int main() {
int n;
std::cin >> n;
// 特殊情况：如果 n=1，只能选 1 个数（即 1 本身）
if (n == 1) {
std::cout << "1" << std::endl;
return 0;
}
int count = 0;
// 贪心策略：选取 1 和所有 <= n 的素数
// 1 和任何数互质。任意两个不同的素数互质。
// 素数和 1 也互质。
// 所以我们统计 2 到 n 之间的素数个数
for (int i = 2; i <= n; i++) {
if (isPrime(i)) {
count++;
}
}
// 最后加上 1（因为 1 也是选取的数）
std::cout << count + 1 << std::endl;
return 0;
}
方法二，埃式筛
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <vector>
// nums 数组用于标记数是否为合数（非素数）
// 0 表示可能是素数（初始状态），1 表示是合数
int nums[100005];
int main() {
int n;
std::cin >> n;
std::vector<int> primes; // 存储找到的素数
// 使用埃氏筛法 (Sieve of Eratosthenes) 找出 2 到 n 的所有素数
for (int i = 2; i <= n; i++) {
// 如果 nums[i] 为 0，说明 i 是素数
if (nums[i] == 0) {
primes.push_back(i);
// 将 i 的倍数标记为合数
// 从 i 开始，每次增加 i (i, 2i, 3i...)
// 注意：这里从 i 开始标记，虽然 i 本身是素数，但标记为 1
// 后不影响后续判断（因为 i 已经处理过了）
for (int j = i; j <= n; j += i) {
nums[j] = 1;
}
}
}
// 贪心策略：选取 1 和所有素数
// 输出素数个数 + 1 (这个 1 代表数字 1)
std::cout << primes.size() + 1 << std::endl;
return 0;
}
方法三，线性筛（欧拉筛）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <vector>
// nums 数组用于标记数是否为合数
// 0 表示是素数，1 表示是合数
int nums[100005];
int main() {
int n;
std::cin >> n;
std::vector<int> primes; // 存储找到的素数
// 使用欧拉筛（线性筛）找出 2 到 n 的所有素数
for (int i = 2; i <= n; i++) {
// 如果 nums[i] 未被标记，说明 i 是素数
if (nums[i] == 0) {
primes.push_back(i);
}
// 遍历已找到的素数，标记 i * p 为合数
for (int p : primes) {
// 如果乘积超过 n，停止标记
if (p * i > n) {
break;
}
nums[p * i] = 1; // 标记 p * i 为合数
// 关键点：如果 i 能被 p 整除，说明 i = k * p
// 那么下一个要标记的数是 i * (下一个素数 p') = k * p * p'
// 这个数会在 i' = k * p' 时被 p 标记，所以这里可以 break
// 保证每个合数只被其最小质因子筛去，达到线性时间复杂度
if (i % p == 0) {
break;
}
}
}
// 贪心策略：选取 1 和所有素数
// 输出素数个数 + 1 (这个 1 代表数字 1)
std::cout << primes.size() + 1 << std::endl;
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
