公式解説と同様に $\displaystyle \binom{N}{K}$ の素因数分解を考えます。

\(10^6\) 以下の素因数について

$\displaystyle \binom{N}{K} = \frac{N!}{K! \left(N-K! \right)}$ より、整数 $m$ について $m!$ の素因数 $p$ における次数を求められればいいです。これは $\lfloor \frac{m}{p} \rfloor + \lfloor \frac{m}{p^2} \rfloor + \cdots + \lfloor \frac{m}{p^z} \rfloor$ ( ただし $z$ は $p^z > m$ を満たす最小の整数 ) に一致するので、これは $O( \log m)$ で求まります。
$n$ が素数かの判定はミラーラビン素数判定法を用いることで $O( \log n )$ でできるので、 $l = 10^6$ 以下の素数の数を $c=78498$ としてこのパートは $O(c \log N + l \log l)$ で行えます。

\(10^6+1\) 以上の素因数について

このような素因数 $p$ の次数は必ず $1$ となります。なぜなら、 $N - (N-K+1) +1 =K$ より $N-K+1$ 以上 $N$ 以下の $p$ の倍数は高々 $1$ つであり、 $p^2 > 10^{12} \geq N$ よりそのような倍数の次数は $1$ となるからです。
よって、公式解説と同様に $N-K+1$ から $N$ までの数を $10^6$ 以下の数で割り、その後 $1$ より大きい数となっている個数を数えればよいです。上と同様に考えることでそのような数は必ず素数になっています。 ( $1$ より大きい数の持つ素因数は必ず $10^6+1$ 以上なので )

実装例(C++)