[GESP202403 五级] B-smooth 数
GESP编程共123题，本题是整站第1403题，已经有人完成了本题，加油！
题目描述
小杨同学想寻找一种名为 B-smooth 数的正整数。
如果一个正整数的最大质因子不超过 B，则该正整数为 B-smooth 数。小杨同学想知道，对于给定的 n 和 B，有多少个不超过 n 的 B-smooth 数。
输入格式
第一行包含两个正整数 n 和 B，含义如题面所示。
输出格式
输出一个非负整数，表示不超过 n 的 B-smooth 数的数量。
输入输出样例
输入 #1
10 3
输出 #1
7
说明/提示
数据规模与约定
| 子任务 | 得分 | n≤ | B |
|---|---|---|---|
| 1 | 30 | 10^3 | 1≤B≤10^3 |
| 2 | 30 | 10^6 | n≤B≤10^6 |
| 3 | 40 | 10^6 | 1≤B≤10^6 |
对全部的测试数据，保证 1≤n,B≤10^6。
别灰心，再试一次！
真题解析
【题目大意】给定n和B，求解有多少个<=n的最大质因子不超过B的B-smooth数
【考纲知识点】唯一分解定理
【解题思路】
①比较朴素的思路为循环遍历1~n,对于每个i，对其分解质因子，得到最大质因子，将质因子和B作比较，并统计到答案中，该算法循环复杂度为O(n),调用分解质因子的复杂度为O(sqrt(n))，总体复杂度为O(nsqrt(n)),加上需要初始化等常数操作，通过1e6的数据是比较危险的。
②考虑在筛法求素数时,对素数P，其倍数都包含素因子P,可以在筛掉素因子P的倍数的同时，用P更新这些倍数的最大素因子。埃式筛法没问题，当然也可以选择欧拉线性筛进一步将复杂度降低为线性。
【参考程序】
本站题目仅供学习，GESP版权归CCF所有，如有侵权请联系删除。站长陈老师QQ及微信:208234。