P 光滑数

题目描述

若一个正整数的所有质因数都不超过 $k$,则称它为 $k$-光滑数。

给定整数 $N$ 和不超过 $100$ 的质数 $P$,求不超过 $N$ 的 $P$-光滑数的个数。

输入格式

输入按以下格式从标准输入给出:

$N$ $P$

输出格式

输出答案(一个整数)。

样例

36 3

14

不超过 $36$ 的 $3$-光滑数有以下 $14$ 个:$1,2,3,4,6,8,9,12,16,18,24,27,32,36$。

注意:对所有质数 $k$,$1$ 都是 $k$-光滑数。

10000000000000000 97

2345134674

数据范围

• $N$ 是满足 $1 \le N \le 10^{16}$ 的整数。
• $P$ 是满足 $2 \le P \le 100$ 的质数。