素直にエラトステネスのふるいの要領で素因数を数える.

素数の発生頻度はおおよそ \(O(\log N)\) なるので, 全体計算量は \(O(N\log N)\) となる. よって, これで間に合う.