Herd Sums(5)

最短コードが狙えるアルゴリズム(中)

2を因数に持っていても解の個数には何も影響しない・・・とすると、その他の因数が解に関わっているわけだ。因数が関係あるということは・・・
因数といえば素因数分解、素因数分解といえば、約数だ。そう思った私は、比較的小さな入力なのに4通りもある、毎回のように例で出している"15"について調べてみた。

15の約数は、

1 3 5 15

すべて奇数だ。

10について調べると、

1 2 5 10

約数は4つあるけど奇数は二つしかない！やはりそうだ！！求めるべき解は、

入力値の約数のうち、奇数であるものの個数

ということか！！！

これならアルゴリズムは超単純だ。1から偶数を飛ばしてループし、その中で入力値を割り切れるものの数をカウントすればよいのだから！！計算量は先のアルゴリズムより多くなるが、オーダーNは決してまずくはない。