2021年になったということで、Pythonプログラミングの要素を絡めて2021に関する記事を書きたいと思います。
Pythonを使って、”2021″を素因数分解してみましょう。素因数分解とは、ある正整数を素数の積の形で表現することです。例えば、10を素因数分解すると2×5に、50を素因数分解すると2×5^2になります。
小さい数であれば暗算で簡単に素因数分解ができますが、2021のように大きな数ではなかなか難しいです。そこで今回は、Pythonを使って一瞬で素因数分解をしてみたいと思います。
基本的な素因数分解アルゴリズムを作ってみる
素因数分解を行うアルゴリズムは多数ありますが、今回は基本的なものを紹介します。
素因数分解を行う際は、もちろんある正整数が素数で割り切れるかどうかを調べる必要があります。例えば10を素因数分解する場合、2,3,5,7と10よりも小さい素数で割っていき、余りが0になるかどうかを調べます。この処理はforループで簡単に実装できそうです。
ではある整数が素数であるかを判定するにはどうすれば良いでしょうか。素数とは、「1とその数自身以外の整数で割り切れない正整数」を指します。素数を判定する際も、forループが活用できます。
まずは、ある整数が素数であるかどうかを判定する関数を作ります。
def prime(a):#aが素数であるかどうかを判定する関数
for i in range(2,a):
if a % i == 0: #割り切れれば、0を返す
return 0
return 1 #素数の場合は、1を返す
素数でない場合は0を、素数の場合は1を返すようにしています。あまりにも桁数が大きい数の場合はこのやり方では難しい場合がありますが、2021程度の大きさであれば問題なく実行できます。
では、この関数prime()を使って、素因数分解を実装していきましょう。
def prime_factorization(a):#aを素因数分解する関数
list_prime = [] #素因数を格納するリストを用意する
for i in range(2,a):
if prime(i):
while True:
if a % i == 0: #素数で割り切れるかどうかを調べる
list_prime.append(i) #割り切れる場合は、リストにその素数を追加する
a /= i
else:
break
if(len(list_prime) == 0): #a自体が素数の場合は、その数をそのまま返す
return a
return list_prime #リストを返すこの関数prime_factorization()（英語で、「素因数分解」という意味）では、リストを返すように設定しています。このリストには、ある正整数の全ての素因数が含まれます。つまり、正整数が10の場合は、[2,5]、50の場合は[2,5,5]が入ったリストが返されます。
途中にwhileループが含まれていますが、これは同じ素因数で何回も割り切れる場合に対応するために設けました。例えば50は5で2回割り切れますが、whileループを入れずに実装すると、[2,5]というリストが返ってきてしまいます。whileを入れて割り切れなくなるまで割り続けることで、正確に素因数分解をすることができます。
また、ある整数が素数である場合にも対応する必要があります。素数は1と自分自身以外の整数では割り切れないので、素因数分解をしても変化が起きません。
ではこれを用いて、2021を素因数分解してみたいと思います。
print(prime_factorization(2021))実行すると、[43,47]というリストが返ってきました。つまり、2021を素因数分解すると、43×47になります。
終わりに
素因数分解という簡単なテーマでしたが、プログラミングを使って計算するのは少し難しかったのではないかと思います。この他にもたくさんの素数判定アルゴリズム、素因数分解アルゴリズムがあるので、興味を持った方はぜひ調べて見てはいかがでしょうか。
