G5006 [GESP202403 五级] B-smooth 数 题解

知识点：质因数、筛法、计数。

解题思路

用素数筛为每个整数记录最大质因数，统计其不超过b的数；1也计入。

为什么正确

每个素数依次覆盖其倍数，最后写入的就是最大质因数，因此判断等价于所有质因数均≤b。

易错点

1没有质因数，按定义满足；不能仅检查数字本身是否≤b。

复杂度

时间O(n log log n)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,b;
    cin>>n>>b;
    vector<int>largest(n+1);
    for(int p=2;p<=n;p++)if(!largest[p])for(int j=p;j<=n;j+=p)largest[j]=p;
    int ans=0;
    for(int i=1;i<=n;i++)ans+=largest[i]<=b;
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用10个自行生成的测试点。