問題一覧 > 通常問題

No.106 素数が嫌い!2

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 224
作問者 : scachescache
7 ProblemId : 158 / 出題時の順位表
問題文最終更新日: 2015-11-14 17:46:57

問題文

素数が嫌いな本田君は、少ない素数で構成される数(相異なる素因数の数が少ない数)をあまり使いたくないです。 そこで、$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

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。