中学の数学 (7-3) 約数を python で探そう

2024年3月18日 16:03

Python で約数をさがそう

約数を探すコード

前回は，約数を探す関数を作りました。次のコードを作成しました。

def divisors(n): 
    print("1") 
    for i in range(2, n): 
        if n % i == 0: 
            print(i) 
    print(n) 

divisors(100000)

n の約数には必ず，1 とnが含まれます。n % 1 や n % n は計算しないで，そのまま出力しました。これで，計算量がすこし減りました。

しかし，もっと減らせそうです。

もっと計算する量を減らそう

例えば，4 の約数を計算しましょう。1 と4 は計算から省きます。

4% 2 = 0
4 % 3 = 1

2 は約数です。４の場合，２より大きい場合は約数ではありません。

次は6の約数を計算しましょう。1 と6は計算から省きます。

6% 2 = 0
6 % 3 = 0
6 % 4 = 2
6 % 5 = 1

2, 3 は約数です。６の場合，３より大きい場合は約数ではありません。

次は8の約数を計算しましょう。1 と8は計算から省きます。

8% 2 = 0
8 % 3 = 2
8% 4 = 0
8 % 5 = 3
8 % 6 = 2
8 % 7 = 1

2, 4 は約数です。８の場合，４より大きい場合は約数ではありません。

以上，３つの例をみてみると，共通して約数にならない場合があります。

４の場合，２より大きい場合は約数ではありません。
６の場合，３より大きい場合は約数ではありません。
８の場合，４より大きい場合は約数ではありません。

なにか規則性がありませんか？

そうですね。n の場合，$${\frac{n}{2}}$$ より大きい数は約数にはならないという規則性があります。

コードを改良しよう

割るというのは，ひとつのものをいくつかに分割するという意味です。割った答えで一番小さいものは 1 ですね。これは$${\frac{n}{n}}$$ を計算した場合にえらえる答えです。

１のつぎに小さい答えは２ですね。これは$${\frac{n}{\frac{n}{2}}}$$を計算したときにえられる答えです。

つまり，n を$${\frac{n}{2}}$$より大きい数で割っても，$${n}$$ を除いて，決して割り切れないことがわかります。

ですから，$${\frac{n}{2}}$$より大きい数で割る場合は考える必要がありません。

def divisors(n): 
    print("1") 
    for i in range(2, n): 
        if n % i == 0: 
            print(i) 
    print(n) 

divisors(100000)

ですから，３行目の for 文で 2 から n-1 まで繰り返す必要はないということです。2 から $${\frac{n}{2}}$$まで繰り返せばいいです。

偶数の場合は $${\frac{n}{2}}$$ は必ず整数になるから，例えば，次のように for 文を直せばそれでいいでしょう。

    for i in range(2, math.floor(n/2)+1):

しかし，奇数の場合はどうでしょう。n が5のとき，$${\frac{n}{2}}$$は 2.5 になります。約数は整数に限られますから，2.5 で割る場合は確認しなくてもよいです。小数は切り捨てて，2 まで計算したいです。

math モジュールを導入する

切り捨てをどう実現するか。自分でコードを書いてもいいでしょう。しかし，今回はすでに作成されている関数を利用することにしましょう。

math モジュールという数学関係の関数が集められたものがあります。これを取り込むことで，便利な関数を使うことができます。

math モジュールを導入するのは，１行目のように，import math とするだけです。

今回使用するのは，math.floor() という関数です。引数に値をいれると，その値の小数点以下の部分を切り捨てた値を返してくれます。math.floor(n/2)の部分で math.floor が使われていることがわかります。

import math

def divisors(n):
    print("1")
    for i in range(2, math.floor(n/2)+1):
        if n % i == 0:
            print(i)
    print(n)

divisors(100)

宿題１

Python には複数の変数をまとめるリストというものが用意されています。リストとはどういうものか。教科書やネットで調べておきましょう。

上のコードは，見つけた約数を標準出力しているだけですが，見つけた約数をリストに入れて，あとで使えるようにするにはどうしたらいいでしょう。