約数の個数が少ない件

Problem 159
素直にやると Σ(約数の個数)/2 ぐらいの時間かかって、でも良いアルゴリズム思いつかないしなぁと放置してたんですが、Cで力まかせにいくかーと思って書いたら1秒くらいで終わって拍子抜けした。

約数の個数って、でかくなりうるイメージが漠然とあったんですが、ちょっと考えてみるだけでも √n くらいで抑えられるんですよね。実際1,000,000までだと最大でも240個で、平均14個とかでした。

調べてみると、n の約数の個数は平均的に O(log log n) とからしい。小さっ!

計算量の見積もりをミスったので猛省。。