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

Pythonによる約数の計算

約数をリストで求める関数

約数を単純に出力する

pythonで約数を求めるプログラムで、もっとも単純で原始的なものを作成します。ここではnum=36の約数を計算しています。numを1から36までの自然数で割り算し、余りが0の場合に出力していきます。

  1. #1 約数を列記する
  2. num = 36
  3. for i in range(1, num+1):
  4. if num % i == 0:
  5. print(i, end=" ")

1 2 3 4 6 9 12 18 36 

  1. 1からnumまでの自然数をiとして発生させるために、3行目以下のfor文でループさせます。range(num)とすると0からnum-1=35までの範囲で計算されてしまうので、range(1, num +1)とします。
  2. 4行目でiで割り算し余りが0のときには、5行目で約数として出力します。
  3. 5行目でprint(i)とすると結果が縦に表示されてしまうので、引数としてend=” ”を指定して横に並べて表示します。

約数をリストで出力する

ここで計算した約数を使って何らかの計算をするときは、リストとして出力しておくと便利です。

  1. #2 約数のリストを作成する
  2. num = 36
  3. divisors = []
  4. for i in range(1, num+1):
  5. if num % i == 0:
  6. divisors.append(i)
  7. print(divisors)

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

3行目でdivisorsというリストを[]で空の状態で定義し、forループの中で約数が見つかったら6行目でリストに約数として追加します。

約数をリストで求める関数

プログラムの中で何度も約数を計算する必要があるときは、次のように関数にしておくと便利です。

  1. #3 約数をリストで返す関数
  2. def divisors_list(num):
  3. divisors = []
  4. for i in range(1, num+1):
  5. if num % i == 0:
  6. divisors.append(i)
  7. return divisors
  8. divisors_list(36)

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

9行目でdivisors_list関数に引数として36を渡すと、約数をリストとして返します。

リスト内包表記やラムダ式による約数の計算

リスト内包表記で約数を計算することができます。リスト内包表記は処理速度が速いといわれています。

  1. #4 リスト内包表記で約数を求める
  2. num = 36
  3. [i for i in range(1, num+1) if num % i == 0]

ラムダ式でも約数を計算することができます。

  1. #5 ラムダ式で約数を求める
  2. num = 36
  3. list(filter(lambda i: num % i == 0, list(range(1, num+1))))

いずれも、前と同じく[1, 2, 3, 4, 6, 9, 12, 18, 36]となります。

効率的な約数の計算

これまで約数の計算をするために、自然数numに対して、1からnumまでの数字をiに順次代入して割り算をし、割り切れる(num%i==0)場合にiを約数と判断ました。36のような小さな自然数であれば問題はありませんが、もっと大きな数字の約数を計算する場合には膨大な計算量になり時間がかかるようになります。そこで、少しでも計算量減らすことを考えます。

約数は対象となる数の半分まで調べれば計算可能

自然数の約数は、次の3つに分けることができます。

(A) 1

(B) 素数でなければそれ以外の約数

(C) 自分自身(num)

1と3は明らかなので、もれなくリストに付け加えることとし、2の計算量を少なくすることを考えます。

  1. #6 約数を返す関数のループを減らして効率化
  2. def divisors_list_h(num):
  3. divisors = [1]
  4. for i in range(2, num//2+1):
  5. if num % i == 0:
  6. divisors.append(i)
  7. if num != 1:
  8. divisors.append(num)
  9. return divisors
  10. divisors_list_h(36)

  1. (A)の1はすべての自然数の約数になるので、3行目でリストを定義するときにセットしておきます。
  2. (B)については、num以外の最大な約数は偶数の場合はnum/2(36であれば18、奇数の場合はnum/3以下(15であれば5)となります。いずれにして自分自身以外の約数を求めるためには、割る数として2からnum/2までテストすることでforループの回数を半分にすることができます。
  3. range(2, num//2+1) としたのは、mum//2と/を切り捨てられた商にしたのはrangeでは整数でないとエラーになるためです。また+1としたのはrange関数では「~まで」の部分は+1する必要があるためです。
  4. (B)の処理が終わったら、(C)のnumも必ず約数になるので8行目でリストに追加します。なおnumを1としたときには、リストの中身に1が2になってしまうことを防ぐために、7行目でnumが1以外であればという条件を入れています。

約数は対象となる数の平方根まで調べれば計算可能

さらに、36の約数を、(1,36)、(2,18) 、(3,12) 、(4,9)、(6,6)と積が自分自身36になるようにペアをつくることができます。これらを同時に求めてリストに追加するようにするとさらに計算量を減らすことができます。

  1. #7 約数を返す関数の相手方も同時に計算することで効率化
  2. def divisor_list_s(num):
  3. divisors = []
  4. for i in range(1, int(num**0.5)+1):
  5. if num % i == 0:
  6. divisors.append(i) #約数をリストに追加
  7. if i**2 == num: #重解の場合に2つリストされるのを防ぐ
  8. continue
  9. divisors.append(num//i) #約数の相手方をリストに追加
  10. # return divisors #昇順にしなくてよいならソートは不要
  11. return sorted(divisors) #昇順にしたいときはソートする
  12. divisor_list_s(36)

  1. 4行目で約数が見つかると、5行目で約数をリストに追加するとともに、8行目でペアの相手方もリストに追加します。例えば約数2が見つかると18もリストに追加しておくわけです。
  2. 6,7行目は36の場合であれば6のように重解があるときは6が2つ追加するのを防ぐためです。continue文は8行目を飛ばして次のループに入ります。
  3. 1,2の工夫をすることにより、for i in range(1, int(num**0.5)+1)というように、1からnumの平方根(0.5乗)までforループを回すことで、すべての約数をリストアップすることができます。
  4. この方法では、[1, 36, 2, 18, 3, 12, 4, 9, 6]のように小さな順番に並びません。8行目のように、return sorted(divisors)とすることで関数の値を返すときに昇順に並び替えることができます。

素因数分解をする

素因数分解の考え方

次に素因数分解をするプログラムを作成します。素因数分解は約数とは異なり、1以外の約数をみつけると、その商がさらにその約数で割り切ることができるか調べる必要があります。例えば、24の素因数分解の場合、約数2を見付けると、商は12、さらに6,4,2とその約数2で割り続ける必要があります。

  1. # 8 素因数分解の結果をリストで列記する関数
  2. def prime_f_list(num):
  3. divisors_l = []
  4. for i in range(2, num+1):
  5. while (num % i) == 0:
  6. num //= i
  7. divisors_l.append(i)
  8. return divisors_l
  9. print(prime_f_list(7776))

[2, 2, 2, 2, 2, 3, 3, 3, 3, 3]

  1. 4行目のfor文で、iを約数の候補として順次調べていきます。
  2. 5行目のwhile文でnum%iで余りが0となり約数であることがわかると、6行目でnumをiで割り7行目でリストに追加します。while文なのでiで割り切れる限り、この操作を繰り返します。
  3. num(+1)まで約数であるかを調べたら、for文を抜けてリストを出力します。
  4. 結果として、素因数分解をした結果をdivisors_lというリストに追加していきます。

素因数分解の結果を見やすくする

素因数分解では素因数を並べる方法もありますが、$7776=2^5*3^5$のように、べき乗を使って表現するのが一般的です。そこで、Pythonの辞書形式で素因数分解をするプログラムを作成します。

  1. #9 素因数分解の結果を辞書形式で求める関数
  2. def prime_f_multi(num):
  3. divisors = {}
  4. for i in range(2, num):
  5. k=0
  6. while (num % i) == 0:
  7. k+=1
  8. num //= i
  9. if k !=0:
  10. divisors[i]=k
  11. if not divisors and num != 1:
  12. divisors[num]=1
  13. return divisors
  14. prime_f_multi(7776)

{2: 5, 3: 5}

因数をi、因数の乗数をkという変数を使って計算します。

  1. whileループを回す中で、約数が見つかった時は7行目でリストに追加することに代えて、kを1だけ増やします。このため2で5回割り切れるときは、k=5となってwhileループを抜けます。
  2. ある約数でこれ以上割り切れなくなるとwhileループを抜けます。ここでiで一度でも割り切れればkは0ではないので、10行目で辞書divisorsに素因数iをキーとして乗数の値kとして追加します。

上記の通り、7776の素因数分解は$2^5×3^5$であることがわかります。ただし、この方法はあまり効率的ではありません。例えばnum=7776を引数とした場合、約数i=2が見つかり、3888、1944と小さくなりその中で約数を見付ければ良いものを、for文ははじめに命令した通りi=7776までループしてしまうためです。つまり、numに約数がある場合には、無駄なループを繰り返すことになるのです。そこで、次節ではwhile文を使ってこの問題を解決します。

for文をwhile文に置き換えて効率化する

ここではwhile文を使い、プログラムを効率化します。

  1. #10 素因数分解を辞書形式で求める関数を効率化(決定版)
  2. def prime_f(num):
  3. divisors={}
  4. i=2
  5. while(i <= num):
  6. k=0
  7. while(num % i == 0):
  8. k+=1
  9. num //= i
  10. if k != 0:
  11. divisors[i]=k
  12. i += 1
  13. return divisors
  14. prime_f(7776)

  1. 5行目をfor文で素因数の候補iをnumまでループさせるのをやめ、iがnumより小さくなるまでループするように変更します。これだけでは何も変わらないような気がしますが、while文にするとループする都度、numとiを比較するので、素因数が見つかる都度numが小さくなり、結果としてループの回数が減ります。
  2. while文を使うために、4行目でi=2として、約数の候補を2から調べるようにします。
  3. ある約数iでの処理が終わったらiに1を加え、より大きな約数を探します。

素因数分解の素因数を見付けるために、for文でもwhile文でも同じ結果を得ることができますが、for文は約数の候補をコントロールするiを順次追加することをしなくてすむ分、効率が悪くなることがあります。一方、while文はiを増やす処理を入れる必要がある分、細かな調整をすることができます。

sympyモジュールによる約数の計算

sympyモジュールで約数や素因数を求める関数

sympyモジュールを使うと、約数の計算を簡単にすることができます。divisors関数に数値を指定すると、約数をリストで、divisor_count関数では約数の数が返されます。

  1. #11 sympyにより約数、約数の個数を計算
  2. import sympy
  3. print(sympy.divisors(7776))
  4. print(sympy.divisor_count(7776))

[1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 72, 81, 96, 108, 144, 162, 216, 243, 288, 324, 432, 486, 648, 864, 972, 1296, 1944, 2592, 3888, 7776]
36

また、factorint関数で素因数分解をすることができます。

  1. #12 sympyにより素因数分解
  2. print(sympy.factorint(7776))

{2: 5, 3: 5}

sympyによる約数に関する関数は次の通りです。

sympyモジュールによる約数の計算
sympy.divisor_count (integer)

数値の約数をリストで返します。

integer
求めたい自然数を指定
sympy.factorint(integer)

数値の約数の数を求めます。

sympy.divisor_count (integer)

数値を素因数分解して結果を辞書形式で帰します。

sympyモジュールの関数と比較することで自作関数を検証する

前作のdivisors_list_h 関数とsympyモジュールのdivisors関数は同じ機能を持っています。そこで、実際に1から100000まで実行して結果を比較します。結果が異なる場合は”ng”、等しい場合は全部プリントすると膨大になるので1000行毎に”ok”を出力するようにします。

  1. #13 約数を求める関数を検証
  2. for i in range(1,100000):
  3. if divisors_list_h(i)==sympy.divisors(i) :
  4. if i%1000==0:
  5. print(i,divisors_list_h(i),sympy.divisors(i),'ok')
  6. else:
  7. print(i,divisors_list_h(i),sympy.divisors(i),'======>ng')

少なくとも100000までは結果が一致することがわかります。同じように、前作のprime_f関数とsympyモジュールのfactorint関数も比較してみます。

  1. #14 素因数分解を辞書形式で求める関数を検証
  2. for i in range(1,100000):
  3. if prime_f(i)==sympy.factorint(i) :
  4. if i%10000==0:
  5. print(i,prime_f(i),sympy.factorint(i),'ok')
  6. else:
  7. print(i,prime_f(i),sympy.factorint(i),'======>ng')

同じように、前作のprime_f関数とsympyモジュールのfactorint関数も結果は同じです。