4615: 【GESP2403五级】B-smooth数

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

题目描述


输入

第一行包含两个正整数$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;
}


#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, B;
    cin >> n >> B;

    // 线性筛求最小质因子
    vector<int> min_prime(n + 1, 0);
    vector<int> primes;
    for (int i = 2; i <= n; ++i) {
        if (min_prime[i] == 0) {
            min_prime[i] = i;
            primes.push_back(i);
        }
        for (int p : primes) {
            if (p > min_prime[i] || i * p > n) break;
            min_prime[i * p] = p;
        }
    }

    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        if (i == 1) {
            // 1 没有质因子，视为 B-smooth
            cnt++;
            continue;
        }
        int x = i;
        int max_factor = 0;
        while (x > 1) {
            int p = min_prime[x];
            if (p > max_factor) max_factor = p;
            while (x % p == 0) x /= p;
        }
        if (max_factor <= B) cnt++;
    }

    cout << cnt << endl;

    return 0;
}

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, B;
    cin >> n >> B;
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        if (i == 1) {
            cnt++; // 1 没有质因子，视为 B-smooth
            continue;
        }
        int x = i;
        int max_factor = 0;
        for (int k = 2; k * k <= x; k++) {
            if (x % k != 0) continue;
            if (k > max_factor) max_factor = k;
            while (x % k == 0) x /= k;
        }
        if (x > 1) max_factor = x;
        if (max_factor <= B) {
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

来源/分类

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