[GESP202403 五级 C++] 27. B-smooth 数 - 题目详情

提交0 通过0

通过率0%

时间限制1000ms

内存限制512MiB

题目描述提交答案

ID: 635

传统题

1000ms

512MiB

难度: 普及-

上传者:

标签>

编程题

c++

素数判断

线性筛法

数论

题目描述

小杨同学想寻找一种名为 $B$ -smooth 数的正整数。

如果一个正整数的最大质因子不超过 $B$ ，则该正整数为 $B$ -smooth 数。小杨同学想知道，对于给定的 $n$ 和 $B$ ，有多少个不超过 $n$ 的 $B$ -smooth 数。

第一行包含两个正整数 $n$ 和 $B$ ，含义如题面所示。

输出一个非负整数，表示不超过 $n$ 的 $B$ -smooth 数的数量。

10 3

子任务编号	数据点占比	n	B
1	30	$\le 1000$	$1\le B\le 1000$
2	30	$\le 10^6$	$\sqrt n\le B\le 10^6$
3	40	$\le 10^6$	$1\le B\le 10^6$

对于全部数据，保证有 $1\le n\le 10^6$ ， $1\le B\le 10^6$ 。