简答题
偏难
#21375
B-smooth 数 题面描述 小杨同学想寻找一种名为B-smooth 数的正整数。 如果一个正整数的最大质因子不超过B,则该正整数为B-smooth 数。 小…
B-smooth 数
题面描述
小杨同学想寻找一种名为B-smooth 数的正整数。
如果一个正整数的最大质因子不超过B,则该正整数为B-smooth 数。
小杨同学想知道,对于给定的n和B,有多少个不超过n的B-smooth 数。
输入格式
第一行包含两个正整数n,B,含义如题面所示。
输出格式
输出一个非负整数,表示不超过n的B-smooth 数的数量。
样例输入
样例输出
样例解释
在不超过10的正整数中,3-smooth 数有{1,2,3,4,6,8,9},共7个。
数据范围

对于全部数据,保证有1≤n≤106,1≤B≤106。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include<bits/stdc++.h>
using namespace std;
int main() {
int n, B;
cin >> n >> B;
assert(1 <= n && n <= 1e6);
assert(1 <= B && B <= 1e6);
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;
}</pre>
这道题暂未补解析。