4615: 【GESP2403五级】B-smooth数

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：2 解决：1

题目描述

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

输入

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

输出

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

样例输入 复制 

10 3

样例输出 复制 

7

提示

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n, B;
    cin >> n >> B;
    vector < bool > vis = vector < bool > (n + 5, false);
    vector < int > mx_prime_factor = vector < int > (n + 5, 0);
    vector < int > prime;
    mx_prime_factor[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            mx_prime_factor[i] = i;
            prime.push_back(i);
        }
        for (int p: prime) {
            if (1ll * p * i > n)
                break;
            vis[i * p] = 1;
            mx_prime_factor[i * p] = max(mx_prime_factor[i * p],
                max(mx_prime_factor[i], p));
            if (i % p == 0)
                break;
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans += (mx_prime_factor[i] <= B);
    cout << ans;
    return 0;
}

来源/分类

提交提交记录统计露一手!