分数: 600 点
问题陈述
正整数称为 k- 平滑数,如果其质因数均不超过 k.
给定一个整数 N 和素数 P 不超过 100,查找数量 P- 平滑数字不超过 N.
约束
- N 是一个整数,使得 1 \le N \le 10^{16}.
- P 是素数,使得 2 \le P \le 100.
输入
输入由标准输入按以下格式给出:
N P
输出
将答案打印为整数。
示例输入 1
36 3
示例输出 1
14
的 3- 平滑数字不超过 36 如下 14 整数: 1,2,3,4,6,8,9,12,16,18,24,27,32,36.
请注意 1 是 k- 所有素数的平滑数 k.
示例输入 2
10000000000000000 97
示例输出 2
2345134674