【GESP】C++五级真题（数论、埃氏筛思想考点） luogu-B3969 [GESP202403 五级] B-smooth 数

GESP C++ 2024年3月五级真题，数论、埃氏筛思想考点，难度⭐⭐★☆☆，属于五级真题中比较简单的。洛谷难度等级普及−

luogu-B3969 [GESP202403 五级] B-smooth 数

题目要求

题目描述

小杨同学想寻找一种名为 $ B $-smooth 数的正整数。

如果一个正整数的最大质因子不超过 $ B $，则该正整数为 $ B $-smooth 数。小杨同学想知道，对于给定的 $ n $ 和 $ B $，有多少个不超过 $ n $ 的 $ B $-smooth 数。

输入格式

第一行包含两个正整数 $ n $ 和 $ B $，含义如题面所示。

输出格式

输出一个非负整数，表示不超过 $ n $ 的 $ B $-smooth 数的数量。

输入输出样例 #1

输入 #1

10 3

输出 #1

7

说明/提示

数据规模与约定

子任务	得分	$n \leq $	$B$
$1$	$30$	$10^3$	$1 \leq B \leq 10^3$
$2$	$30$	$10^6$	$\sqrt n \leq B \leq 10^6$
$3$	$40$	$10^6$	$1 \leq B \leq 10^6$

对全部的测试数据，保证 $1 \leq n, B \leq 10^6$。

---

题目分析

解题思路

核心思想：先筛出所有 $\leq B$ 的质数，再用“埃氏筛”思想把这些质数的倍数全部标记为 $B$-smooth，最后统计标记个数。

1. 先线性筛出所有 $\leq B$ 的质数，得到“允许质因子”集合。
2. 用埃氏筛思想：把上述质数的所有倍数都标记为 $B$-smooth。
3. 若某数被 $>B$ 的质数整除，则其最大质因子必 $>B$，故撤销该数的 $B$-smooth 标记。
4. 最后统计被标记的个数，并额外加上 $1$（因为 $1$ 恒为 $B$-smooth）。

---

示例代码

#include <iostream>

// 标记数组：nums[i]=1 表示 i 是 B-smooth 数，反之不是
int nums[1000005];

// 判断 x 是否为质数
bool is_prime(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; ++i)
        if (x % i == 0) return false;
    return true;
}

int main() {
    int n, B;
    std::cin >> n >> B;

    int count = 0;                 // 当前 B-smooth 数个数
    for (int i = 2; i <= n; ++i) {
        if (i <= B && is_prime(i)) {
            // i 是 ≤B 的质数，将其倍数全部标记为 B-smooth
            for (int j = i; j <= n; j += i) {
                if (nums[j] == 0) {   // 首次被标记
                    nums[j] = 1;
                    count++;
                }
            }
        }
        if (i > B && is_prime(i)) {
            // i 是 >B 的质数，其倍数都不再是 B-smooth，撤销标记
            for (int j = i; j <= n; j += i) {
                if (nums[j] == 1) {   // 之前被标记过
                    nums[j] = 0;
                    count--;
                }
            }
        }
    }
    // 1 恒为 B-smooth，故结果 +1
    std::cout << count + 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)，考试认证学员交流，互帮互助

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