【Python】約数を計算してみる

この記事では、Pythonで約数を計算する方法を解説します。

約数を求めること自体はとても簡単ですが計算方法によってかなり処理の重さが異なってきます。そういう部分にも意識を向けながら実装方法を見ていきましょう!!

約数の基本
計算量を半分に減らす
平方根でさらに減らす
まとめ

約数の基本

約数とは「ある整数を割り切れる整数のこと、またはそれらの集合のこと」を言います。例えば、16の約数は「1、2、4、8、16」となります。

Pythonで実装するには、for文を使って1から指定された整数までのループを作成し、指定された整数を割り切れる値を抜き出すことで約数を求めることができます。

# 指定された整数 n = 16 for i in range(1, n + 1): # 割り切れるかどうかの判定 if n % i == 0: # 割り切れた場合にその値を出力 print(i)

実行結果

1 2 4 8 16

range(1, n + 1) のところで n に 1 を足している理由は、range() は 1 から指定された値の1つ手前までしかループ処理してくれないため

このままだと使いづらいので関数に直しておきます。

def divisor(n: int) -> None: for i in range(1, n + 1): # 割り切れるかどうかの判定 if n % i == 0: # 割り切れた場合にその値を出力 print(i)

結果をリストで受け取りたい場合は、以下のようにします。

def divisor(n: int) -> list[int]: # 約数を格納するリストを用意 result = [] for i in range(1, n + 1): # 割り切れるかどうかの判定 if n % i == 0: # 割り切れた場合にその値をリストに格納 result.append(i) # 最後に約数が格納されたリストを返す return result

内包表記を使うことでもっとシンプルに実装することもできます。

def divisor(n: int) -> list[int]: return [i for i in range(1, n + 1) if n % i == 0]

Link内包表記の種類と使い方を解説

これがPythonで約数を計算する一番簡単な方法です。ただし、この実装方法では無駄な部分まで計算してしまっているのでかなり遅いです。

なので、次に計算量を減らす方法を見ていきましょう。

計算量を半分に減らす

約数は指定された整数の半分まで計算すれば求めることができます。つまりは、range()でループする範囲を半分にします。

def divisor(n: int) -> list[int]: result = [] # n の半分の範囲でループ処理 for i in range(1, n // 2 + 1): if n % i == 0: result.append(i) # n まで到達しないので最後に自身を追加しておく result.append(n) return result

ちなみに//演算子は小数点以下を切り捨てつつ、商を求めることができる便利な演算子です。float型にも変換されないのでそのまま指定することができます。

r = 16 // 2 + 1 print(r, type(r)) # 9 <class 'int'>

もちろん、内包表記でも可能です。

def divisor(n: int) -> list[int]: result = [i for i in range(1, n // 2 + 1) if n % i == 0] result.append(n) return result

通常の半分の計算で済んだので実際に速度を比べてみたら大体半分ぐらいになりました。

# 速度を測るのに必要なライブラリ import time # 関数の実行時間を測るデコレータ def func_speed(func): def _wrapper(*args, **keywargs): start_time = time.time() result = func(*args, **keywargs) print('time: {:.9f} [sec]'.format(time.time() - start_time)) return result return _wrapper @func_speed def divisor(n: int) -> list[int]: return [i for i in range(1, n + 1) if n % i == 0] @func_speed def divisor2(n: int) -> list[int]: result = [i for i in range(1, n // 2 + 1) if n % i == 0] result.append(n) return result n = 10000000 divisor(n) # time: 0.260249615 [sec] divisor2(n) # time: 0.130022049 [sec]

Link任意の処理の実行時間を測る方法

平方根でさらに減らす

実は約数を求めるには平方根までのループで十分です。約数は１つ見つけるとその値を使ってもう１つの約数を求めることができます。例として16の約数で考えてみます。

16の約数である1が計算できたら 約数を求める整数 / 約数 をすることで対の約数を割り出せます。つまり、1の対となる約数は16です。この調子で計算していくと(2, 8)、(4, 4) となり、平方根までのループですべての約数を求めることができます。

Pythonで平方根を求めるには**演算子を使います。**演算子はべき乗することができ、指数に0.5を指定することで平方根を求めることができます。

print(1 ** 0.5) # 1.0 print(2 ** 0.5) # 1.4142135623730951 print(4 ** 0.5) # 2.0 print(16 ** 0.5) # 4.0

そんなこんなで実装してみると以下のようになります。ポイントとしては平方根と対となる約数が同じになったらbreakすることです。これしないと同じ値がリストに格納されてしまいます。

def divisor(n: int) -> list[int]: result = [] # 平方根の計算 root = int(n**0.5) # 平方根までをループ処理 for i in range(1, root + 1): if n % i == 0: result.append(i) # 対となる約数の計算 b = n // i # 平方根と対となる約数が同じになったらbreak if root == b: break # 対となる約数をリストに追加 result.append(b) # 最後にソートしたリストを返す return sorted(result)

さて、それでは速度を比べてみます。

# 速度を測るのに必要なライブラリ import time # 関数の実行時間を測るデコレータ def func_speed(func): def _wrapper(*args, **keywargs): start_time = time.time() result = func(*args, **keywargs) print('time: {:.9f} [sec]'.format(time.time() - start_time)) return result return _wrapper @func_speed def divisor(n: int) -> list[int]: return [i for i in range(1, n + 1) if n % i == 0] @func_speed def divisor2(n: int) -> list[int]: result = [i for i in range(1, n // 2 + 1) if n % i == 0] result.append(n) return result @func_speed def divisor3(n: int) -> set[int]: result = [] root = int(n**0.5) for i in range(1, root + 1): if n % i == 0: result.append(i) b = n // i if root == b: break result.append(b) return sorted(result) n = 1000000000 # 通常 d1 = divisor(n) # time: 25.465010405 [sec] # 半分 d2 = divisor2(n) # time: 12.672288895 [sec] # 平方根 d3 = divisor3(n) # time: 0.000982523 [sec]

めちゃくちゃ高速化することができました。