約数を求める

はじめに

AtCoderの問題を解いていた時、計算量を減らすコードの書き方を学習しました。

学んだことをアウトプットしようと思い、記事を書きました。

コード

a = 1000
divisor1 = []
#計算量の多いコード
for i in 1..a do
    if a%i==0
        divisor1<<i
    end
end

#計算量の少ないコード
divisor2 = []
a_root = Math.sqrt(a).floor

for i in 1..a_root do
    if a%i==0
        divisor2 << i
        divisor2 << a/i
    end
end

解説

1000の約数を求めるコードを書いています。

計算量を減らすポイントは平方根を利用することです。

(1,1000),(2,500)などのかけたら1000になる組み合わせのペアを考えます。平方根は整数のペアの小さい数の最大値になります。

つまり、1から平方根までの数を全探索すれば、整数のペアをすべて求めることができます。

そうすることで、コンピューターの計算量を減らして約数を全て求めることができます。

おわりに

平方根を利用することで計算量を減らす方法を学習しました。この方法は、約数を求めること以外にも応用が利きそうだと感じました。