题目描述

$k$ 以下の素数のみを素因数に持つ正整数を $k$-smooth number と呼びます。
整数 $N$ および $100$ 以下の素数 $P$ が与えられるので、 $N$ 以下の $P$-smooth number の個数を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $P$

输出格式

答えを整数として出力せよ。

题目大意

一个正整数被称为“$k$ 阶平滑数”，当且仅当它的任意一个素因子不超过 $k$。

给定正整数 $N$ 和素数 $P$。问不超过 $N$ 的“$P$ 阶平滑数”有多少个。

36 3

14

10000000000000000 97

2345134674

提示

制約

• $N$ は $1\ \le\ N\ \le\ 10^{16}$ を満たす整数
• $P$ は $2\ \le\ P\ \le\ 100$ を満たす素数

Sample Explanation 1

$36$ 以下の $3$-smooth number は $1,2,3,4,6,8,9,12,16,18,24,27,32,36$ の $14$ 個です。 $1$ は任意の素数 $k$ に対して $k$-smooth number であることに注意してください。