競プロ典型90問 030 コード 問題 素直にエラトステネスのふるいの要領で素因数を数える. 素数の発生頻度はおおよそ \(O(\log N)\) なるので, 全体計算量は \(O(N\log N)\) となる. よって, これで間に合う.