编程题第 2 题25 分

B-smooth 数

时间限制 1 秒 · 内存限制 512 MB

题目描述

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

如果一个正整数的最大质因子不超过 $B$ ，则该正整数为 $B$ -smooth 数。

小杨同学想知道，对于给定的 $n$ 和 $B$ ，有多少个不超过 $n$ 的 $B$ -smooth 数。

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

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

输入

10 3

输出

在不超过 $10$ 的正整数中， $3$ -smooth 数有 $\{1, 2, 3, 4, 6, 8, 9\}$ ，共 $7$ 个。

子任务编号	数据点占比	$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$ 。

数据范围

子任务编号	数据点占比	$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$ 。