OneCoder Avatar
OneCodercoderli.com · 1026 篇博文
五级

C++ 算法考级专栏

🎨 视觉封面

【GESP】C++五级真题(数论、贪心考点) luogu-P14073 [GESP202509 五级] 数字选取

📅 2025-11-24·✍️ OneCoder·计算中...·⏱️ 10 分钟

GESP C++ 2025年9月五级真题,数论、贪心考点,题目难度⭐⭐★☆☆,五级来说难度相对简单。洛谷难度等级普及−

luogu-P14073 [GESP202509 五级] 数字选取

题目要求

题目描述

给定正整数 ,现在有 共计 个整数。你需要从这 个整数中选取一些整数,使得所选取的整数中任意两个不同的整数均互质(也就是说,这两个整数的最大公因数为 )。请你最大化所选取整数的数量。

例如,当 时,可以选择 共计 个整数。可以验证不存在数量更多的选取整数的方案。

输入格式

一行,一个正整数 ,表示给定的正整数。

输出格式

一行,一个正整数,表示所选取整数的最大数量。

输入输出样例 #1

输入 #1
PLAINTEXT1 行
6
输出 #1
PLAINTEXT1 行
4

输入输出样例 #2

输入 #2
PLAINTEXT1 行
9
输出 #2
PLAINTEXT1 行
5

说明/提示

对于 的测试点,保证 。

对于所有测试点,保证 。


题目分析

这道题主要考察数论中的互质概念以及贪心策略。

核心思想

题目要求在 到 中选取尽可能多的整数,使得任意两个整数互质(最大公因数为 1)。

一、关于 1 的特性:

和任何正整数的最大公因数都是 。因此,为了最大化数量,我们一定选取 1。

二、关于大于 1 的数:

对于两个大于 的整数 和 ,如果它们互质,意味着它们不能有共同的质因数。换句话说,如果我们选出的集合中包含 个大于 的整数,那么这 个整数每一个至少包含一个质因数,且这些质因数必须两两不同(否则就会有公因数)。

为了让选出的数最多,我们希望每个数“消耗”的质因数尽可能少。每个大于 的数至少有一个质因数。消耗最少的情况就是每个数本身就是一个质数(只包含一个质因数)。

如果我们选取一个合数(例如 ),它占用了 和 两个质因数的“位置”。如果我们选了 ,就不能选 、3、8 等等。显然,不如直接选取质数 和 更划算(选了 和 只是不能选它们的倍数,但我们获得了 个数,而选 只有 个数)。

贪心策略

综上所述,最优的选取方案是:

  1. 选取数字 1。
  2. 选取 到 之间的所有素数(质数)。

最终答案即为: 以内素数的个数 + 1。

算法选择

根据 的范围(),我们需要一种高效的方法来统计素数个数。

  1. 试除法:对每个数判断是否为素数。单次判断 ,总复杂度 。对于 勉强可过,但不是最优。
  2. 埃氏筛 (Sieve of Eratosthenes):时间复杂度 ,效率较高,适合本题。
  3. 线性筛 (Euler Sieve):时间复杂度 ,效率最高,适合更大范围的数据。

本题数据范围 ,三种方法均可通过。


示例代码

方法一,试除法

C++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;
}

方法二,埃式筛

C++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;
}

方法三,线性筛(欧拉筛)

C++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;
}

看完题解去实战!OneCoder C++ 信奥远征闯关平台 (oi.coderli.com)
💡 OneCoder 资源指引

所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI

🤝 技术交流与答疑

欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。

📚

猜你想读 · 相关文章推荐

OneCoder

OneCoder

一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

读者讨论与留言

共 0 条讨论
邮箱必填 · 支持 Markdown 格式与直接回复
💬 还没有读者留言,快来成为第一个讨论者吧!