はじめに
以前作成した「Pythonで入力された数字が素数か判定するプログラム」に、合成数だった場合に素因数分解を行ってくれる機能を追加してみました。
プログラムの原理
小学生の時に習った素因数分解のやり方を思い出して、小さい素数から順に割り続ける方針にしました。
具体的には、SymPyのprimerangeを用いて素数リストを作成し、そのリストから割り切れる数で割り続けます。そして、素数リストの最後まで割り算を行ったら終了としました。
実際のプログラム
from sympy import primerange
inn = n = int(input("素数か確かめたい数を入力してください。>> "))
primlist = list(primerange(2,(inn+1) / 2)) #1
yaku = []
for i in primlist:
while n % i == 0: #2
n /= i
yaku.append(i) #3
if not yaku: #4
print(n, "は素数です。")
else:
print(inn, "は合成数で、素因数分解すると",yaku, "です。")
大まかな流れ
- 素数リストを (n+1)/2 まで作成
- 素数リストの中から割り切れる数を探し、割り切れなくなるまで整数 n を割り続ける。
- 割るたびに yaku というリストに割った素数を追加していく。
- yaku に何も入っていなければ素数と表示する。なにか入っていれば素因数分解した結果を表示。
実際にやっていること
- #1で、前回同様Sympyを用いて作成。
- #2で、while構文を用いることで、ifを使わずに直ぐに割り続ける動作に入れるようしてあります。
- #3で、.append(i) とすることで yaku に割った素数の i を追加します。
- #4で、yaku に数が入っていれば、合成数であるということに注目しました。具体的には if 構文を用いて、if not yaku とすることで yaku に何も入っていない際に、if より下の処理に入ります。
苦労した点
はじめにプログラムした際、primerange()で作成する素数リストの範囲を、前回と同じ「primerange(2, int(n**(1/2)) + 1)」としていました。すると、入力された整数が "2×素数" の場合に2のみが yaku に追加されて正確に素因数分解できない問題が発生しました。 具体的には14 (2×7) のような数字を入力した際に結果として『14 は合成数で、素因数分解すると [2] です。』と出てしまいました。
そのため素数リストの範囲を「primerange(2, (inn+1) /2)」に設定しました。こうすることで先程の問題の解決としました。この際、inn に +1 をすることで "2×素数" の整数でも素数リストが素数まで作られるようになっています。具体的には14を入力した際にprimerange(2, 7.5)となるため、primelistの中身が [2, 3, 5, 7]となります。もし+1をしないと、primerange(2, 7)となるため、primelistの中身が [2, 3, 5]となってしまい、7が素因数分解の結果に入らないことになり、正確な素因数分解ができなくなります。
反省点
素数リストの作成の範囲が広すぎるために、入力される整数が大きくなる(7桁以上)と、とたんに計算速度が落ちます。そのため範囲の設定や素因数分解の方式を少し改善したい思います。
最後まで読んで下さいまして有難うございました。