Nに素数を順に加算して最も近い素数を求めるCプログラム

本記事では、数値Nが素数でない場合に、2から始まる素数を順番に加算していき、最も近い素数を見つけ出す問題について解説します。

入力：N=6
出力：11

処理の流れ

まず、入力された数値Nが素数かどうかを判定します。例としてN=6を考えてみましょう。6は素数ではないため、最初の素数である2を加算します。すると6+2=8となりますが、8もまた素数ではありません。そこで、2の直後の素数である3を加算すると、8+3=11となります。11は素数であるため、これが出力結果となります。

アルゴリズム

処理の全体像は、以下の擬似コードのとおりです。外側のループで候補となる数kが素数かどうかを判定し、素数であれば現在の合計値numに加算します。その後、更新されたnumが素数かどうかを再度チェックし、素数であればそれを出力して処理を終了します。

開始
ステップ1：変数num=15、i=num/2を宣言する
ステップ2：k=2からk<=iまで、kを1ずつ増やしながら繰り返す
　　l=k/2を設定する
　　j=2からj<=lまで、jを1ずつ増やしながら繰り返す
　　　　flag=0を設定する
　　　　もしk%j==0ならば
　　　　　　flag=1を設定する
　　　　　　ループを抜ける
　　　　ここまで
　　ここまで
　　もしflag==0ならば（kが素数の場合）
　　　　num=num+kを設定する
　　ここまで
　　a=num/2を設定する
　　m=2からm<=aまで、mを1ずつ増やしながら繰り返す
　　　　flag1=0を設定する
　　　　もしnum%m==0ならば
　　　　　　flag1=1を設定する
　　　　　　ループを抜ける
　　　　ここまで
　　ここまで
　　もしflag1==0ならば（numが素数の場合）
　　　　numを出力する
　　ここまで
ここまで
停止

C言語による実装例

以下は、初期値を15とした場合のC言語による実装例です。

#include<stdio.h>
int main(){
   int num =15 ;
   int i,k,j,sum=0,flag=0,l,flag1=0,a,m;
   i=num/2;
   for(k=2;k<=i;k++) {
      l=k/2;
      for(j=2;j<=l;j++) {
         flag=0;
         if(k%j==0) {
            flag=1;
            break;
         }
      }
      if(flag==0) {
         num=num+k;
      }
      a=num/2;
      for(m=2;m<=a;m++) {
         flag1=0;
         if(num%m==0) {
            flag1=1;
            break;
         }
      }
      if(flag1==0){
         printf("%d",num);
         return 0;
      }
   }
}

実行結果

上記のプログラムを実行すると、以下の出力が得られます。

17

この結果は次のように説明できます。初期値15に対して、最初の素数である2を加算すると17になります。17は素数であるため、その時点で結果が出力され、プログラムは終了します。