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

· · 题解

解题思路

这道题目的数据范围有点大，暴力算法的时间复杂度是 O(n^2) 的，明显超时，于是我们可以先预处理出 1\sim n 的所有数的最大质因子。但是暴力找到最大质因子也是很慢的，所以我们可以先筛出每个数的最大质因子，最后统计一下即可。

为什么可以用筛法呢？因为例如数字 6，他的质因子有 2 和 3，于是它在 i = 2 时被处理了一次。当 i = 3 时，由于他是 3 的倍数，所以它又被处理了一次，最后我们算出它的最大质因子为 3。

注意：虽然 1 没有质因子，但是也要算入答案。

CODE:

#include <bits/stdc++.h>
using namespace std;
int a[1000010];
int ans;
int main() {
    int n, b;
    cin >> n >> b;
    a[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!a[i]) {
            for (int j = i; j <= n; j += i)
                a[j] = i;
        }
    }
    for (int i = 1; i <= n; i++) { 
        if (a[i] <= b)
            ans++;
    }
    cout << ans;
    return 0;
}