https://www.acmicpc.net/problem/11439

$N$ 이하의 모든 소수에 대해 $\binom{n}{k}$에 들어있는 인자의 갯수를 구해 해결하는 방법도 있고, $\binom{n}{k}$을 계산할 때 $M$과 서로소인 파트와 서로소가 아닌 파트를 나눠 해결하는 방법도 있습니다. 저는 후자로 해결했지만 전자가 속도도 빠르고 코드 길이도 짧습니다.

https://github.com/blisstoner/BOJ/blob/master/11439.cpp