🕌

【初心者向け 110】約数アルゴリズム

2023/12/04に公開

アルゴリズムノート（Python）

自然数を割り切る数です。
割り切るとは、商だけが存在し、余りがないことを意味します。

例えば、自然数10を2で割ると考えてみましょう。

例）10 / 2 = 5 ... 0
10を2で割ると商は5、余りは0です。
余りが0という意味は余りがないという意味と同じですので、2は10の約数です。

これをコードで表すと 10 % 2 == 0 となります。
つまり、N % i == 0 ならば、iはNの約数です。

n = int(input())
arr = []

for i in range(1, n + 1):
  if n % i == 0:
    arr.append(i)

print(arr)  # 約数のリスト
print(len(arr))  # 約数の個数

a * b = Nならば、aとbはN（自然数）の約数です。

10 / 2 = 5 ... 0なので、商は5、余りは0、約数は2であることが証明されました。
ここで約数である2と商である5を掛けると？
2 * 5 == 10となる現象が観察できます。
ここからわかることは2つあります。

約数（2）と商（5）をかけると、所属する自然数（10）になります。
「a * b = Nならばa, bは約数」の公式が適用されるため、2と5はどちらも約数であることがわかります。
つまり、N % i == 0 ならばiだけでなくN//iも約数です。

n = int(input())
arr = []

for i in range(1, n + 1):
  if n % i == 0:
    arr.append(i)
    arr.append(n // i)

ただし、このコードは重複した数が存在するため修正が必要です。
[1, 10], [2, 5], [5, 2], [10, 2]のように約数が2回ずつ含まれるためです。

a * b = Nならば、2つの約数aとbは対称です。
a * a = Nならば、aは約数であり平方根でもあります。つまり、平方根も約数です。

10の約数は[1, 2, 5, 10]であり、1 x 10、2 x 5が10であることがわかります。
注目すべきは距離です。

100の約数を再度観察してみましょう。
[1, 2, 4, 5, 10, 20, 25, 50, 100]
この場合も最も近い1と最も遠い100が対称し、その隣にある2, 50も対称していることがわかります。

また、重要なポイントとして中央にある10は対称する数が存在しないことです。
しかし、10を2乗すると100になります。
このように同じ数を2乗してNになると、その同じ数がNの平方根であり、約数にも含まれることがわかります。

したがって、任意の自然数Nの約数を求めたい場合、まず自然数Nの平方根までだけ繰り返します。
約数2で示したように残りの約数（20, 25, 50, 100）は商を通じて追加すれば良いです。

n = int(input())
arr = []

for i in range(1, int(n**(1/2)) + 1):
  if n % i == 0:
    arr.append(i)
    if i * i != n:
      arr.append(n // i)