Pythonで約数を計算する

約数を計算する関数

Pythonで正の整数の約数を求める関数を作りました。詳しくは次の通りです。

Pythonによる約数の計算と素因数分解

def divisors_list_h(num):
   divisors = [1]
   if  num == 1:
       return divisors
   for i in range(2, num//2+1):
       if num % i == 0:
           divisors.append(i)
   divisors.append(num)
   return divisors

print(divisors_list_h(36))

結果
[1, 2, 3, 4, 6, 9, 12, 18, 36]

このようにリストで計算されます。この方法によると求める数の1/2までfor文でループする必要があります。一方、次の方法によると、求める数の平方根までループすることで計算することができます。

def divisors_list_s(num):
   divisors = []
   for i in range(1, int(num**0.5)+1):
       if num % i == 0:
           divisors.append(i)  
           if i**2 == num:
               continue
           divisors.append(int(num/i))
   return divisors # 昇順にしなくてよいならソートは不要
#     return sorted(divisors) # 昇順にしたいときはソートする

print(divisors_list_s(36))

結果
[1, 36, 2, 18, 3, 12, 4, 9, 6]

小さい順番に並びませんが、ループの回数を減らすことができます。36程度の整数の約数であれば差はありませんが、10,000になると前者の5,000回に対し後者は100回と大きな差になります。

1から15までの全ての整数を約数に持つ数

この関数を使って、360,360の約数を計算します。

print(divisors_list_h(360360))

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 
18, 20, 21, 22, 24, 26, 28, 30, 33, 35, 36, 39, 40,
42, 44, 45, 52, 55, 56, 60, 63, 65, 66, 70, 72, 77,
78, 84, 88, 90, 91, 99, 104, 105, 110, 117, 120,
126, 130, 132, 140, 143, 154, 156, 165, 168, 180,
182, 195, 198, 210, 220, 231, 234, 252, 260, 264,
273, 280, 286, 308, 312, 315, 330, 360, 364, 385,
390, 396, 420, 429, 440, 455, 462, 468, 495, 504,
520, 546, 572, 585, 616, 630, 660, 693, 715, 728, 770,
780, 792, 819, 840, 858, 910, 924, 936, 990, 1001, 1092,
1144, 1155, 1170, 1260, 1287, 1320, 1365, 1386, 1430, 1540,
1560, 1638, 1716, 1820, 1848, 1980, 2002, 2145, 2184, 2310,
2340, 2520, 2574, 2730, 2772, 2860, 3003, 3080, 3276, 3432,
3465, 3640, 3960, 4004, 4095, 4290, 4620, 4680, 5005, 5148,
5460, 5544, 5720, 6006, 6435, 6552, 6930, 8008, 8190, 8580,
9009, 9240, 10010, 10296, 10920, 12012, 12870, 13860, 15015,
16380, 17160, 18018, 20020, 24024, 25740, 27720, 30030, 32760,
36036, 40040, 45045, 51480, 60060, 72072, 90090, 120120, 180180, 360360]

360,360は1から15の全ての整数を約数とする最小の数になります。ちなみに192もの約数を持ちます。

このように、1からnまでの約数をもつ最小の数を求めるときは、1からnまでの最小公倍数を計算すればよいことになります。最小公倍数はsympyモジュールのilcmで計算することができます。

from functools import reduce
for i in range(2,25):
   print(i,reduce(sympy.ilcm, range(1,i+1)))
   
2 2
3 6
4 12
5 60
6 60
7 420
8 840
9 2520
10 2520
11 27720
12 27720
13 360360
14 360360
15 360360
16 720720
17 12252240
18 12252240
19 232792560
20 232792560
21 232792560
22 232792560
23 5354228880
24 5354228880   

１から16の約数を持つ最小の数は720720になるのですね。こんなことも簡単に計算できるPythonの素晴らしさを改めて感じました。

なお、最小公倍数については次を参照してください。

Pythonで最小公倍数、最大公約数を計算する

余談

書類の整理をしていたら、昔書いたメモが見つかりました。

十歳では菓子に、二十歳では恋人に、三十歳では快楽に、四十歳では野心に、五十歳では貪欲に動かされる。人間はいつになったら、英知のみを追うようになるのだろうか。
ジャン・ジャック・ルソー『エミール』

メモを書いたのは相当昔ですが、いつのまにか60歳になってしまいました。果たして英知のみを追うように生きているか、自省しながら日々を過ごしています。