演習(第二回)の解答例

演習問題 1 (素数 - prime number)

1. 割算の余り(剰余)の出力
   自然数 j をひとつ入力して, 1 から j までの整数で j を割った 余りを順番に出力するプログラム (冒頭の宣言などは省略 - 以後も)

   青色の部分が重要箇所を示している.

   int main(void){
     char buf[80];
     int j;
     int i;
     int k;
   
     gets(buf);
     j = atoi(buf);
     for(i=1; i<=j; i++){
       k = j % i;
       printf("%d %% %d = %d\n", j, i, k);
     }
   }
   

2. 約数だけを出力
   ループの中で条件に合う場合だけ処理を行なうことが要点.

   int main(void){
     char buf[80];
     int j;
     int i;
     int k;
   
     gets(buf);
     j = atoi(buf);
     for(i=1; i<=j; i++){
       k = j % i;
       if(k == 0){
         printf("%d\n", i);
       }
     }
   }
   

3. 約数の個数を出力
   個数を数える時には, そのための変数(ここでは n)を用意して, 初期値ゼロを与えておく. あとは, 条件が成立した場合だけ n = n + 1 (これは n++ と書いても同じ) を行なうことで, ループが終了した時点での個数が n に残る.

   int main(void){
     char buf[80];
     int j;
     int i;
     int k;
     int n;
   
     gets(buf);
     j = atoi(buf);
     n = 0;
     for(i=1; i<=j; i++){
       k = j % i;
       if(k == 0){
         n = n + 1;
       }
     }
     printf("%d\n", n);
   }
   

4. 素数かどうかを出力
   前のプログラムで, ループ終了時の約数の個数 n が 2 (1と自分) であることを判断しているだけ.

   int main(void){
     char buf[80];
     int j;
     int i;
     int k;
     int n;
   
     gets(buf);
     j = atoi(buf);
     n = 0;
     for(i=1; i<=j; i++){
       k = j % i;
       if(k == 0){
         n = n + 1;
       }
     }
     if(n == 2){
       printf("%d is prime\n", j);
     } else {
       printf("%d is not prime\n", j);
     }
   }
   

5. 計算の手間を改善
   
   • j の平方根以下の約数がないなら, それより大きな約数もないはず.
   • j が奇数の場合, 偶数の約数を持つことはありえない.
   j の平方根を計算するのは面倒なので「i の二乗が j 以下である」という条件に 置き換えている(これなら四則計算でできる). また, 偶数か奇数かの判断を最初にやってしまうことで, 奇数を 2 で割ってみるという無駄な計算を省いている.

   int main(void){
     char buf[80];
     int j;
     int i;
     int k;
     int n;
   
     gets(buf);
     j = atoi(buf);
     if(j % 2 == 0){		/* 偶数の場合 */
       if(j == 2){
         printf("%d is prime\n", j);
       } else {
         printf("%d is not prime\n", j);
       }
     } else {			/* 奇数の場合 */
       n = 0;
       for(i=3; (i*i)<=j; i += 2){
         /* 除数の範囲を, j の平方根までの奇数に限定 */
         k = j % i;
         if(k == 0){
   	n = n + 1;
         }
       }
       if(n == 0){
         printf("%d is prime\n", j);
       } else {
         printf("%d is not prime\n", j);
       }
     }
   }
   

   さらに, 割り切れる場合がひとつでも見つかったらその先を計算しないプログラム. 「break文」は教科書 P.201 に説明があるが, 現在実行中のループから イキナリ脱出するためのものである.

   int main(void){
     char buf[80];
     int j;
     int i;
     int k;
     int n;
   
     gets(buf);
     j = atoi(buf);
     if(j % 2 == 0){		/* 偶数の場合 */
       if(j == 2){
         printf("%d is prime\n", j);
       } else {
         printf("%d is not prime\n", j);
       }
     } else {			/* 奇数の場合 */
       n = 0;
       for(i=3; (i*i)<=j; i += 2){
         /* 除数の範囲を, j の平方根までの奇数に限定 */
         k = j % i;
         if(k == 0){
   	n = n + 1;
   	break;			/* 割り切れたらfor文から脱出 */
         }
       }
       if(n == 0){
         printf("%d is prime\n", j);
       } else {
         printf("%d is not prime\n", j);
       }
     }
   }
   

演習問題 2 (連続する整数の和)

前の問題同様, 段階的に考えてみる.

1. i から j までの連続する整数の和
   

   int main(void){
     char line[80];
     int i,j, sum;
     int k;
   
     gets(line);
     i = atoi(line);
   
     gets(line);
     j = atoi(line);
   
     sum = 0;
     for(k=i; k<=j; k++){
       sum = sum + k;
     }
   
     printf("%d + ... + %d = %d\n", i, j, sum);
   }
   

   等差数列の和の公式を使ってsumを一気に計算するなら, 青色の部分は

     sum = (i+j)*(j-i+1)/2;
   

   とすればよい. (そしてこちらの方が繰り返しがないぶん高速)

2. j は入力して, i の方を 1 から (j-1) まで変化させるプログラム

   int main(void){
     char line[80];
     int i,j, sum;
   
     gets(line);
     j = atoi(line);
   
     for(i=1; i<j; i++){
       sum = (i+j)*(j-i+1)/2;
       printf("%d + ... + %d = %d\n", i, j, sum);
     }
   }
   

   合計の計算は等差数列の和の公式を使うことにした.

3. 入力としては, j の上限となる値を与え, i と j のすべての組み合わせに ついて「連続和」を求めるプログラム
   二つの変数のすべての組み合わせを処理するには, 二重のループを用いる. ここでは, 外側のループで j を変化させ, その j に対して内側のループで i を変化させている.

   int main(void){
     char line[80];
     int i,j, sum;
     int max_j;
   
     gets(line);
     max_j = atoi(line);
   
     for(j=1; j<=max_j; j++){
       for(i=1; i<j; i++){
         sum = (i+j)*(j-i+1)/2;
         printf("%d + ... + %d = %d\n", i, j, sum);
       }
     }
   }
   

4. そもそもの問題をとくプログラム.
   前のステップの連続和がちょうど n になる時だけ出力すればできあがり.

   int main(void){
     char line[80];
     int i,j, sum;
     int n;
   
     gets(line);
     n = atoi(line);
   
     for(j=1; j<=n; j++){
       for(i=1; i<j; i++){
         sum = (i+j)*(j-i+1)/2;
         if(n == sum){
   	printf("%d + ... + %d = %d\n", i, j, sum);
         }
       }
     }
   }