約数の列挙

　プログラミングコンテストでは、与えられた整数 n の約数を列挙させるような出題があります。そこで今回は、その約数を列挙させるpython3 のコードを紹介します。

以下のコードは、n = 25 として、その約数を配列 mylist に格納するものです。

#(1)
import math
#(2)
n = 21
mylist = []
#(3)
check_range = int(math.sqrt(n))  # √n
#(4)
for i in range(1, check_range + 1):
    if n % i == 0:
        mylist += [i]
        if n//i != i:
            mylist += [n//i]
print(mylist)
# --> [1, 21, 3, 7]

それでは、上記コードの内容を個別にみていきます。

#(1)
import math
#(2)
n = 21
mylist = []

(1) の部分は、(3)の部分で math.sqrt( )を使用するので、インポートしています（その内容は以下で触れます）。
また、(2) の部分で、今回約数を列挙しようとしている整数 n と、その約数を格納する配列 mylist を定義しています。

#(3)
check_range = int(math.sqrt(n)+1)  # √n

(3)の部分で、 math.sqrt( ) を使って 変数 check_range を計算します。実際の約数の探索は、n に対して 1から順に割り切れるかを確かめていきます。その時に、割る数は n まで確かめる必要はありません。なぜなら 21 / 3 = 7 があったとして、このときに、3 と 7 をmylist に格納しておけば、　21 / 7 = 3 を改めて確かめる必要はありません。よって割る数は、n の平方根までとなり、その値を check_range としています。

#(4)
for i in range(1, check_range + 1):
    if n % i == 0:
        mylist += [i]
        #(5)
        if n//i != i:
            mylist += [n//i]
print(mylist)
# --> [1, 21, 3, 7]

(4) の部分で、約数の探索を実際に行います。for ループの範囲は、 (3) で取得した check_range +1 としなくてはならない事に注意して下さい。(5) の部分では　例えば　n = 25 の場合、25 / 5 = 5 となり、5 が重複して mylist に格納されることを防ぐための処理です。