素因数分解してルートの中を簡単にするプログラムを書いてみた

スポンサーリンク

 

こんにちは!HELLO!您好!привет там ! 안녕하세요 !Hola !

新学期ですね。

大学新入生の皆様、ご入学おめでとうございます。

特に情報系学科の同志のみんな!おめでとう!心より。

ただ、浮かれてないで早くプログラミングの勉強を進めた方がいいぞ。白目。

とっくに勉強してると思うけど。白目

と言うのも僕は大学に入学してからプログラミングの勉強を始めた人間で、大学1年の初めの頃はプログラムが

  1. 読めない
  2. 書けない
  3. 分からない
  4. 帰りたい

のフルコンボみたいな状況に陥って苦しんだ経験があるからです。

プログラミング経験が全くない状態で大学の授業に臨むと流石にきつかったです。個人的に。

me

今ではプログラミングが趣味と言えるほどコーディングを楽しんだり

次は何の言語を勉強しようかなとワクワクしたりする余裕がありますが、

こういう境地に至るまで地味に時間がかかりました。

 

で、毎年この季節になると無意識に思い出してしまうプログラムがいくつかあります。

最近思いつきでそのプログラムを書き直してみたので今日はそれを紹介します。

結構適当で力任せなプログラムで下手な書き方をしていますが部分的にはある程度参考になるかと思います。

 

プログラムの仕様とソースコード

与えられた√内の数値を簡単にして最も簡単な√表示に変換するプログラムを書きました。

以下の3点のプロセスに基づきプログラムを実装します。

  1. 素数判定をしてリストアップする
  2. 素因数分解をする
  3. 素因数に基づいて√から外に出す

大学1年のプログラミングの小テストなどで出題される程度のレベルではありますがちょっとした復習になります。

me

とりあえずプログラムをここに貼り付けておきますが、下の方でアルゴリズムや実装方法などの簡単な説明をしますので興味がある方はどうぞ。

 

実行例 1実行例 2実行例 3実行例 4実行例 5

C:\Users\yukiWavy\mycpp>root
x: 8
root 8 = 2 root 2
<Prime Factors>
2: 3

C:\Users\yukiWavy\mycpp>root
x: 81
root 81 = 9
<Prime Factors>
3: 4

C:\Users\yukiWavy\mycpp>root
x: 17
root 17 = root 17
<Prime Factors>
17: 1

C:\Users\yukiWavy\mycpp>root
x: 111111
root 111111 = root 111111
<Prime Factors>
3: 1
7: 1
11: 1
13: 1
37: 1

C:\Users\yukiWavy\mycpp>root
x: 45
root 45 = 3 root 5
<Prime Factors>
3: 2
5: 1



特定範囲内の素数をピックアップする

プログラムの仕様上、素因数分解を行う際の素数配列が欲しかったので、入力された値以下の素数をピックアップして配列に格納する関数を作成しました。

この処理にあたり2つの関数を用意します。isPrime と listPrimeNumAryです。

isPrime関数は引数に与えられた値が素数か否かを判定する関数で、

listPrimeNumAry関数は引数に与えられた値以下の素数を実際に配列に格納する関数です。

素数判定のアルゴリズムはこちらの記事を参照ください。

C++で素数判定のプログラムを実装する

2017.10.30

コードの処理内容はコメントアウトの通りです。

 

素因数分解をする

素因数分解のアルゴリズムや実装法はいくつもありますがここでは最も単純で力任せな方法で実装します。

中学校の数学の教科書で扱われているポピュラーな素因数分解の方法です。

素因数分解を以下のような書き方で行ったことがあるかと思います。

商が 1 になるまで素数で割り続ける方法です。

この方法をそのまま実装します。

 

ルートの中身を簡単にする

素因数分解の結果を元にそれぞれ素因数の個数を 2 で割った商の数だけその値はルートの外にでることができます。

ある素因数が 1 個の場合はルート内に残ります。

ルートの外側と内側との場合に分けてべき乗計算をベースにそれぞれの結果を掛け合わせてながら素因数の種類だけ繰り返すことでルートの中身を簡単にすることができます。

 

以上で簡単なプログラムの説明は終わりです。

ですがここで説明したプログラムはあくまで参考程度のもので優れた実装方法は他にたくさんあると思います。

また、今回は単純に力任せで素因数分解を行いましたがより実践的なポラード・ロー素因数分解という方法があります。

興味がある方はぜひ勉強して実装してみてはいかがでしょうか?

 

ということで「新入生のみんな入学おめでとう!」の回はこれにて。

プログラミングを始めたばかりだとコンパイルエラーとかコンパイルエラーとかコンパイルエラーとかで色々謎が深かったり肩や目が痛くなったりで辛いこともあるかもしれないけど、

それも含めてプログラミングって本気で楽しいから頑張ろう!

ではまた!

スポンサーリンク


ABOUT ME

yuk!

国立大学情報学科に通う大学生です。天然パーマと戦いながらすーぱーエンジニアを目指し技術とセンスを磨いています。 室内に引きこもりがちでヘビメタと猫と甘いものが救いのキーボードカチャカチャ生活ですが、最近はブログで文章を書くことが楽しいです。モットーは「 Who dares wins. = 人生是一箇,活殺全在我。」好きな言葉は「マジ卍」。