Max Composite N

$2 \leq X \leq 10 ^6 = M$とおきます。$1$から$M$の整数それぞれがいくつ約数を持つかを数えます。

任意の自然数$n$の約数が$m$個あることは、倍数に$n$のある自然数は$m$個ある、と言い換えられます。 そこで、以下の操作を行います。

• 長さ$M$の配列$c$を作り、$c_x$は整数$x$の約数の個数を保持する。
• $1 \leq x \leq M$において、$c_{y} \ (y = x, 2x, ..., rx )$を$1$ずつ増やす。($r$は、$rx \leq M < (r + 1) x$を満たします。)

この操作は$O(M \log{M})$で行えます。

$c$を生成した後は$c_x$の値ごとに$x$を分け、$k_i = c_x$を満たす$x$を昇順に並べた配列を二分探索することなどにより、制限時間内にこの問題を解くことができます。