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

· · 题解

题意分析

这道题的目标非常简单，就是要求我们求出 1 到 n 中最大质因数不超过 B 的自然数的数量。

时间复杂度分析

本题的时间数据范围为 1 \le n,B \le 10^6，需要用 O(n) 的复杂度才能通过。

解题思路

方法一：暴力

我们可以对 1 到 n 的每一个数都暴力枚举一遍。但是，时间复杂度达到了 O(n^2)，所以只能拿到40分。

方法二：埃氏筛

推荐在做这道题目之前先看看这一道模版题。\ 对于这个算法的详细证明，可以查看 学委 的 这篇文章，非常感谢作者的贡献！\ 对于这道题目，我们在数组里记录的是最大的质因数而非0或1，最后再判断是否不超过 B 即可。\ 算法复杂度为 O(n)，可以满分通过。

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+7;
int n,B;
int MaxP[N];
int main(){
    cin >> n >> B;
    MaxP[1]=1;
    for(int i=2; i<=n; i++){
        if(!MaxP[i]){
            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;
    return 0;
}