030 - K Factors(★5)
解説
/
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点: 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