[GESP202403 五级] B-smooth 数
题目描述
小杨同学想寻找一种名为 $ B $-smooth 数的正整数。
如果一个正整数的最大质因子不超过 $ B $，则该正整数为 $ B $-smooth 数。小杨同学想知道，对于给定的 $ n $ 和 $ B $，有多少个不超过 $ n $ 的 $ B $-smooth 数。
输入格式
第一行包含两个正整数 $ n $ 和 $ B $，含义如题面所示。
输出格式
输出一个非负整数，表示不超过 $ n $ 的 $ B $-smooth 数的数量。
样例 #1
样例输入 #1
10 3
样例输出 #1
7
提示
数据规模与约定
| 子任务 | 得分 | $n \leq $ | B B B |
|---|---|---|---|
| 1 1 1 | 30 30 30 | 1 0 3 10^3 103 | 1 ≤ B ≤ 1 0 3 1 \leq B \leq 10^3 1≤B≤103 |
| 2 2 2 | 30 30 30 | 1 0 6 10^6 106 | n ≤ B ≤ 1 0 6 \sqrt n \leq B \leq 10^6 n ≤B≤106 |
| 3 3 3 | 40 40 40 | 1 0 6 10^6 106 | 1 ≤ B ≤ 1 0 6 1 \leq B \leq 10^6 1≤B≤106 |
对全部的测试数据，保证 1 ≤ n , B ≤ 1 0 6 1 \leq n, B \leq 10^6 1≤n,B≤106。
C++实现
#include <bits/stdc++.h>
using namespace std;
int a[1000010];
int ans;
int main() {
int n, b;
cin >> n >> b;
a[1] = 1;
for (int i = 2; i <= n; i++) {
if (!a[i]) {
for (int j = i; j <= n; j += i)
a[j] = i;
}
}
for (int i = 1; i <= n; i++) {
if (a[i] <= b)
ans++;
}
cout << ans;
return 0;
}
后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
标签：10,信奥,int,30,smooth,B3969,leq,打卡,106 From： https://blog.csdn.net/rogeliu/article/details/144491963