目次

• はじめに
• python
• java
• C
• 追記（高速化）

はじめに

個別塾のバイト中に素因数分解を教えていて，
「素因数分解は繰り返しのためコンピュータが処理を得意そう」
と感じたためプログラムを実装してみました

python

まずはpythonです

実行

$ python3 PrimeFactorization.py
素因数分解したい整数を入力してください：1024
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

1024を素因数分解することができました

java

続いて、同じ内容をjavaでやってみました

出力

$ javac PrimeFactorization.java
$ java PrimeFactorization
素因数分解したい整数を入力してください：1024
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

先にコンパイルするの懐かしいです
変数や配列や関数の型の指定の不要なpythonって楽な言語だと改めて実感しました

C

c言語でもやってみました

実行

$ gcc PrimeFactorization.c -o app   
$ ./app
素因数分解したい整数を入力してください：1024
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

c言語での可変配列がよくわからなかったので、因数を順番にprintfで出力するようにしました
printfですら型の指定が必要なCは大変ですね…
実行は速いですが…（この程度のプログラムじゃ差はない）

追記（高速化）

AtCoderでプログラミングをして遊んでいたところ，素因数分解の問題が出てきたので，
お！そのまま使えるやん！と上記のプログラムをしたところ…

上のように「遅すぎwwww」と煽られてしまったので， 整数$n$の因数は$\sqrt{N}$までしかないことを活用して高速化してみました．（関数化はしておらず，表示のために数字をstringで保存しています．）

AtCoderくんもご満悦です🤗