[GESP202403 五级] B-smooth 数(B-Smooth Numbers) 题解

思路分析

使用埃氏筛或线性筛在 $O(n \log \log n)$ / $O(n)$ 时间内预处理 $2 \sim n$ 每个数的最大质因子 maxP[i]（每次筛素数 $p$ 时对所有倍数更新 maxP[j] = p）。注意 $1$ 没有质因子，对任意 $B \ge 1$（包括 $B = 1$），$1$ 都是 $B$-smooth 数（令 maxP[1] = 0）。最后统计 $1 \le i \le n$ 中满足 maxP[i] <= B 的个数即可。

参考代码

#include <iostream>
using namespace std;

const int MX = 1000005;
int maxP[MX];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, B;
    if (!(cin >> n >> B)) return 0;
    for (int i = 2; i <= n; ++i)
    {
        if (maxP[i] == 0)
        {
            for (int j = i; j <= n; j += i) maxP[j] = i;
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (maxP[i] <= B) ++ans;
    }
    cout << ans << "\n";
    return 0;
}