配点: 5 点
問題文
2 以上 N 在以下整数中,K 查找具有不止一种质因数的事物的数量。
制約
- 2 \leq N \leq 10^7
- 1 \leq K \leq 8
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N K
出力
请打印答案。 到达
入力例 1
15 2
出力例 1
5
例如,4=2^2 是质因数 1 不满足条件,因为它有一个类型, 6=2\times 3 是质因数 2 满足条件,因为它有类型。
满足条件。 仅6,10,12,14,15 可以得到第 5 件。
入力例 2
30 2
出力例 2
13
满足条件。 仅6,10,12,14,15,18,20,21,22,24,26,28,30 可以得到第 13 件。
入力例 3
200 4
出力例 3
0
入力例 4
869120 1
出力例 4
869119
入力例 5
10000000 3
出力例 5
6798027