题解

时间复杂度O(n sqrt(n)) 1e6应该过不了的，acgo数据水

#include<bits/stdc++.h>
using namespace std;

int n, b, ans;

// 判断a是否为B-smooth数，最大质因子<=b
bool isp(int a, int b) {
    for (int i = 2; i * i <= a; i++) {
        if (a % i == 0) {
            if (i > b) return 0;
            // 除尽当前质因子
            while (a % i == 0) a /= i;
        }
    }
    // 循环结束后，若剩余a>1，说明剩余的数是a最后一个质因子
    return a <= b;
}

int main() {
    cin >> n >> b;
    // 遍历统计所有符合条件的数
    for (int i = 1; i <= n; i++) {
        if (isp(i, b)) ans++;
    }
    cout << ans;
    return 0;
}