← 返回题目列表

AtCoder · abc300_g

G. P-平滑数

中文机器翻译题面 查看原题

分数: 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