昔のプログラミング初学者向けの本の定番である「素因数分解」。著者は親しみや興味が出るからだろうとこのテーマを選んだと思われます。しかし、思いっきりすべっている感もあります。
中学生の数学で習ったし、暗号とかの話にも繋がる素数や素因数分解ですが、正直つまらないし、昔習ったことなど忘れています。
まあ、そんな話より素因数分解を思い出しながら記事を読んでみて下さい。
素因数分解って？
与えられた数字をとにかく整数で割りまくって行くことです。最終的には全部の数字が素数になります。あっ、素数って何？ 聞かれそうだが素数とは
「その数と１以外で割り切れない数」
のことです。皆さん大好きなセブンイレブン、７と１１を例にすると
と、１と７以外では割り切れません。１１も
と、１と１１以外では割り切れません。
素因数分解に話を戻して、例えば３０を割り切れるだけ割り切ると
２☓３☓５
となります。ここで出てきた２，３，５は全て素数です。このように全て素数に分解することを素因数分解と呼びます。多分というか絶対に中学一年の最初の数学で習っています。
プログラムで書くとどうなるか？
以下がプログラムで書いた素因数分解です。
- #include<stdio.h>
- int main(void)
- {
- int num,i;
- printf("Enter Natural Number?");
- scanf("%d",&num);
- if(num<0)
- {
- printf("Error %d is not Natural number.\n");
- return 1;
- }
- printf("Factoring\n");
- if(num==1)
- {
- printf("%d\n",num);
- }
- else
- {
- for(i=2;i<=num;i++)
- {
- if(num%i==0)
- {
- printf("%d ",i);
- num/=i;
- i=1;
- }
- }
- }
- return 0;
- }
やっていることは、とにかく割り切れる数字が見つかるまでひたすら割っていくことをやっています。ただ、このプログラムは分かりにくいです。
理由としてはコメントが入っていないことです。これは置いておきます。
次にやたら唐突に出てくる数字が多いところです。ただ、0や1は唐突に出しても良いと妥協されています。それ以外の数字だと
- １５行目に num=1 とある
- ２１行目にi=2
- ２７行目はi=1なのだが、どうして途中で１なのか？
という部分があります。そうだ、ツッコミはやめてほしいのですけど、目的は素因数分解を極めることでは無いので総当たりのループです。
多少わかりやすくしてみました
以下は修正したプログラムです
- #include<stdio.h>
- const int ciOne = 1; //やりすぎかもしれないが1も定義
- const int ciFirstPrime = 2; //最初の素数は２
- int main(void)
- {
- int num,i;
- printf("Enter Natural Number?");
- scanf("%d",&num);
- if(num<0)
- {
- printf("Error %d is not Natural number.\n");
- return 1;
- }
- printf("Factoring\n");
- /* １が入力された場合はエラーではないが素因数分解の例外として１を出力して処理を終了
- あまりエレガントでは無いが、数学でもそういうルールなので*/
- if(num==ciOne)
- {
- printf("1\n",num);
- return 0;
- }
- //数字が１になるまで現在の数を割り続ける。内側のループは最初の素数２から現在の数−１までループ、割り切れたらその数字を出力し、それで割った数を現在の数とする。
- while(num != ciOne){
- for(i=ciFirstPrime;i<=num;i++)
- {
- if(num%i==0) //数字が割り切れたなら
- {
- printf("%d ",i);
- num/=i;
- break;
- }
- }
- }
- return 0;
- }
コメントが入っているのでズルいだろ？ って言われそうですけどそれ以外で直したポイントを説明します。
まず、１という数字が入れられた場合は特例として処理します。メインのループで１を考慮するのも複雑性を上げるだけなので除外しています。
プログラミングの罠として、全て一般化したルールで実装したいという衝動に駆られますが、それにより可読性を下げたり、アルゴリズムが複雑になることは避けたいので特例のパターンは先に抜いておくことをおすすめします。
次に決め打ちの数字１，２を定数として定義しています。２、３行目で const int とある場所です。定数をプログラムの途中に配置すると後でわからなくなるので最初に定義して名前として使うのが良いです。今回は１はciOne、２はciFirstPrimeと定義しています。
34行目にbreakとありますが、一度ループから出ています。そして、その外のループで再び中に入っています。前回のプログラムではループ変数 i=1 と代入されていますが、この１は後でプラス１されて２になることを意図しています。しかし、分かりにくいのでこの方法はやめています。唐突な数字を代入されるより、breakでループを出るという考えの方がわかりやすくミスも有りません。
最後にコメントは、何を処理しているかを重点的に書いています。C言語は読めることを前提にしていますので、コードを見れば分かることは書いていません。
話はずれますが、プログラミングの解説書にかかれているコメントはプログラムを学習するためのコメントですので、本来の書き方とか異なります。決して i=1 のコメントとして「iに１を代入する」なんて書いてはいけないです。 どういう意図で代入するかを必ず書いて下さい。
以上、簡単なプログラムをわかりやすく書く方法の説明でした。
