202509-数字选取(luogu-P14073)

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

输入输出样例 #2

输入 #2

输出 #2

说明/提示

对于 $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$ ，三种方法均可通过。

示例代码

方法一，试除法

#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;
}

方法二，埃式筛

#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;
}

方法三，线性筛（欧拉筛）

#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;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号

最后更新于 2025年11月26日

202506-最大公因数(luogu-P13014)202509-有趣的数字和(luogu-P14074)