A33230. B-smooth 数
填空题
困难
知识点
题目描述
B-smooth 数
题目描述
小杨同学想寻找一种名为 B-smooth 数的正整数。
如果一个正整数的最大质因子不超过 B，则该正整数为 B-smooth 数。
小杨同学想知道，对于给定的 n 和 B，有多少个不超过 的 B-smooth 数。
输入格式
第一行包含两个正整数 n,B，含义如题面所示。
输出格式
输出一个非负整数，表示不超过n 的 B-smooth 数的数量。
样例1
10 3
7
样例解释
在不超过 10 的正整数中， B-smooth 数有 {1,2,3,4,6,8,9}，共 7 个。
数据范围
对于全部数据，保证有 1≤ n ≤ 1000000，1≤ B ≤1000000 。
参考答案
#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;
}
上一题
下一题