中学の数学 (7-3) 約数を python で探そう
[ サイトマップを見る ]
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 は約数です。4の場合,2より大きい場合は約数ではありません。
次は6の約数を計算しましょう。1 と6は計算から省きます。
6% 2 = 0
6 % 3 = 0
6 % 4 = 2
6 % 5 = 1
2, 3 は約数です。6の場合,3より大きい場合は約数ではありません。
次は8の約数を計算しましょう。1 と8は計算から省きます。
8% 2 = 0
8 % 3 = 2
8% 4 = 0
8 % 5 = 3
8 % 6 = 2
8 % 7 = 1
2, 4 は約数です。8の場合,4より大きい場合は約数ではありません。
以上,3つの例をみてみると,共通して約数にならない場合があります。
4の場合,2より大きい場合は約数ではありません。
6の場合,3より大きい場合は約数ではありません。
8の場合,4より大きい場合は約数ではありません。
なにか規則性がありませんか?
そうですね。n の場合,$${\frac{n}{2}}$$ より大きい数は約数にはならないという規則性があります。
コードを改良しよう
割るというのは,ひとつのものをいくつかに分割するという意味です。割った答えで一番小さいものは 1 ですね。これは$${\frac{n}{n}}$$ を計算した場合にえらえる答えです。
1のつぎに小さい答えは2ですね。これは$${\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)
ですから,3行目の 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 モジュールを導入するのは,1行目のように,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)
宿題1
Python には複数の変数をまとめるリストというものが用意されています。リストとはどういうものか。教科書やネットで調べておきましょう。
上のコードは,見つけた約数を標準出力しているだけですが,見つけた約数をリストに入れて,あとで使えるようにするにはどうしたらいいでしょう。
関連する書籍
[ サイトマップを見る ]
この記事が気に入ったらサポートをしてみませんか?