No.106 素数が嫌い!2

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 179
作問者 : scachescache
4 ProblemId : 158 / 出題時の順位表

問題文

素数が嫌いな本田君は、少ない素数で構成される数(相異なる素因数の数が少ない数)をあまり使いたくないです。 そこで、$2〜N$までの数字のうち素因数を$K$個以上持つ数しか使わないことにしました。しかし、使える数が少なすぎるのは嫌だと思ったので、あらかじめいくつの数を使うことができるかを調べておくことにしました。

$N$と$K$が与えられた時、使用できる数の個数を出力してください。

入力

N K

入力は整数で与えられる。
$2 \le N \le 2,000,000=2\times 10^6$
$1 \le K \le 100$

出力

$2$以上$N$以下の数で相異なる素因数の数が$K$個以上の数の個数を出力してください
最後に改行してください。

サンプル

サンプル1
入力
2 1
出力
1

サンプル2
入力
4 2
出力
0


2,3,4の中で素因数を2つ以上持つ数はないので答えは0である

サンプル3
入力
1000 4
出力
23

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。