-smooth 数

题目描述

⼩杨同学想寻找⼀种名为 -smooth 数的正整数。 如果⼀个正整数的最⼤质因⼦不超过 ，则该正整数为 -smooth 数。 ⼩杨同学想知道，对于给定的 和 ，有多少个不超过 的 -smooth 数。

输入格式

第⼀⾏包含两个正整数 ，含义如题⾯所⽰。

输出格式

输出⼀个⾮负整数，表⽰不超过 的 -smooth 数的数量。 3.2.4 样例1 1 10 3 1 7 3.2.5 样例解释 在不超过 的正整数中， -smooth 数有 ，共 个。 3.2.6 数据范围 子任务编号 数据点占比 1 2 3 对于全部数据，保证有 ， 。 3.2.7 参考程序 1 #include<bits/stdc++.h> 2 using namespace std; 3 4 int main() { 5 6 int n, B; 7 cin >> n >> B; 8 assert(1 <= n && n <= 1e6); 9 assert(1 <= B && B <= 1e6); 10 11 vector vis = vector(n + 5, false); 12 vector mx_prime_factor = vector(n + 5, 0); 13 vector prime; 14 mx_prime_factor[1] = 1; 15 for (int i = 2; i <= n; i ++) { 16 if (! vis[i]) { 17 mx_prime_factor[i] = i; 18 prime.push_back(i); 19 } 20 for (int p : prime) { 21 if (1ll * p * i > n) 22 break ; 23 vis[i * p] = 1; 24 mx_prime_factor[i * p] = max(mx_prime_factor[i * p], max(mx_prime_factor[i], p)); 25 if (i % p == 0) 26 break ; 27 } 28 } 29 30 int ans = 0; 31 for (int i = 1; i <= n; i ++) 32 ans += (mx_prime_factor[i] <= B); 33 cout << ans; 34 return 0; 35 }

样例输入 #1

1 10 3
1 7

样例输出 #1

样例解释 #1

在不超过 的正整数中， -smooth 数有 ，共 个。

数据范围

子任务编号 数据点占比 1 2 3 对于全部数据，保证有 ， 。

知识点与难度

本题涉及的知识点从属于 GESP 5级，难度等级：⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。