AT_abc300_g [ABC300G] P-smooth number
题目描述
仅以不超过 $k$ 的素数作为素因数的正整数被称为 $k$-smooth 数。
给定整数 $N$ 和不超过 $100$ 的素数 $P$，请你求出不超过 $N$ 的 $P$-smooth 数的个数。
输入格式
输入通过标准输入按以下格式给出。
> $N$ $P$
输出格式
请输出答案，结果为一个整数。
说明/提示
## 限制条件
- $1 \leq N \leq 10^{16}$
- $2 \leq P \leq 100$，且 $P$ 是素数
## 样例解释 1
不超过 $36$ 的 $3$-smooth 数有 $1,2,3,4,6,8,9,12,16,18,24,27,32,36$ 共 $14$ 个。请注意，$1$ 对于任意素数 $k$ 都是 $k$-smooth 数。
由 ChatGPT 4.1 翻译