【Java】入力された数字の素数を表示するプログラムについて(階乗、素因数分解も)【面接】


 
はいどーも!
てりやきです。

転職活動の際の面接にて、
素数表示するプログラム書け、というテストが何回かありました。
その時に書いたものを記録としてこの投稿に残しておきたいと思います。

 

ポイント

 

プログラム内にコメントも残してますがポイントは、

1. 2以外の偶数に素数は無い
2. 今までの発見した素数で割る
3. 割るのは対象の数の平方根まで

という感じですたぶん。
特に3の平方根の判定を入れるか入れないかで、
1000000を入力した時の素数出力までの時間が30秒くらい変わりました。平方根大事です。

 

ソースコード

 

 

なんとなくmain関数で入力を受け付けるとことか書いてますが、
extractSosuという関数がプログラムのメインです。
あとなんとなくロシア語でユーザーからの入力を促してます。

他にも面接のテストで素因数分解や階乗を表示せよという問題があったので、
あとでそれについても投稿しようと思います。
 

追記(2017/05/06):
と思ったのですが、
既に完全なるJavaでの見本がネットにありましたのでそのサイトのリンクを貼っておきます。

素因数分解↓
『【Java】素因数分解をする』
http://fantom1x.blog130.fc2.com/blog-entry-213.html

階乗↓
『お気楽 Java プログラミング入門 第 4 回 再帰定義』
http://www.geocities.jp/m_hiroi/java/abcjava04.html

素数に関してはなんとなく「これだ!」っていうのが見つからなかったので自分で書いてみたのですが、
素因数分解と階乗は上述のサイトが「まさにこれだ!」って感じでした。

面接のテストで出てきたプログラミング問題についてはこれで終わります。
また新たな面白い問題に出会ったら投稿します。

 
Posted by てりやき
Twitter→@teriyakiegg

Comments are closed.