C言語入門 5 (素数を扱う 2)

素数を求めるC言語のプログラム

これからも、C言語のもつ各機能(関数や制御文)や長所を活かしたプログラムを公開したいと思っていますが、
C言語入門記事は一旦この記事で締めたいと思います。

前回に引き続き素数を扱うプログラムの紹介とその解説、またアルゴリズムという概念についても触れます。

今回作成するプログラムでは「指定した数字以下に含まれる素数を全て表示する」ことを目的としています。

今回取り組むこと

  1. プログラムの仕様
  2. アルゴリズムについて
  3. エラトステネスの篩
  4. プログラム
  5. まとめ

1 プログラムの仕様

今回の目的は 「指定した数字以下に含まれる素数を全て表示する」ことです。

入出力の関係でいえば、
入力:1より大きい自然数(数字ひとつ)
出力:入力された数字以下に含まれる素数(数字複数、数は不明)
という形になります。出力する先はprintfで表示できる標準出力にします。(黒い画面にそのまま表示します。)

2 アルゴリズムという言葉

アルゴリズムはズバリ、
「とあるタスクを(確実に)こなすための手順」です。

具体例をいくつか出してみましょう。

アルゴリズムの具体例1:料理のレシピ

料理のレシピはれっきとアルゴリズムのひとつです。

からあげを作ろうと思ってレシピを見ます。
(例えば、こちらの鶏のから揚げ(AJINOMOTO レシピ大百科より))
この手順を踏めばかならず「から揚げを作る」というタスクを達成できます。

アルゴリズムの具体例2:ならびかえ

トランプを順番通りに直すように数字を大きい順(もしくは小さい順)に並び替えるようなタスクは、
頻繁に用いられる上に、いくつも手段があり、それぞれ長所短所があるので「アルゴリズムの具体例」としても人気です。

並び替えることを英語でソート(Sort)と言いますが、これをおこなうアルゴリズムを「ソートアルゴリズム」と言い、
Google検索してみると実に多くの情報に触れられると思います。

ソートアルゴリズムは頻繁に使うのでその効率のよさが特に重要視されます。

効率の良さには主に2つの見方があり、「計算する回数」と「どれほどメモリを使うか」に注目します。
計算する回数はなんとなく想像しやすいかと思うので説明を省きます。
ではメモリの面での効率とは?イメージをつかむためにソートで考えてみましょう。
一度にたくさんの数字を見れば早く並び替え終わりそうなものですが、その場合見た数字を覚えないといけません。
その分、一時的な記憶力がなければそのタスクは十分に達成できません。

アルゴリズムの具体例3:その他

私の拙い説明よりもわかりやすいページも多くありますが、
宇野毅明さんのアルゴリズムとは何か(一般向け)の説明が一般向けということもあり大変わかりやすいです。
また例ではありませんが様々な既存のアルゴリズムを可視化したVisuAlgoというwebサイトは、
もちろん勉強にもなりますが何より見ていて楽しいのでおすすめです。

3 エラトステネスの篩

「エラトステネスの篩(ふるい)」は古代ギリシャくらい昔に誕生したとされるアルゴリズムのひとつです。

このアルゴリズムは「指定された数以下の素数を全て見つける」ものです。
したがってこのアルゴリズムに従えば「指定された数以下の素数を全て見つける」ことが確実にできます。(くどい)

wikipediaのgifアニメーションが非常によくできています(かつ見ていて楽しい)。

手順を以下に示します。

  1. 数字を指定する
  2. 2から指定した数字を並べて、これを探索リストとする
  3. 先頭の数字は素数なので探索リストに残す
  4. 先頭の数字の倍数を探索リストから除外する
  5. 3&4のステップを先頭の数字が1で指定した数字の√より大きなったら終了
  6. 探索リストに残ったものが素数

4つめのステップで探索リストから数字をふるい落とすイメージから「篩(ふるい)」という名前がついたのでしょう。
これはものすごくスマートなアルゴリズムです。
対して、前回の記事では、入力された数字が素数かどうか判断するために、
入力された数字までの数すべてで割り切れるかかどうかを調べました。

4 プログラム

#include <stdio.h>
#include <math.h>

#define N 200	// この数字以下の素数を求める

int main(void){
	int targetArray[N];	// 探索リスト
	int i, j, k, l;
	
	/* 初期化 */
	targetArray[0] = 0;
	for(i=1; i <= N; i++){
		targetArray[i]=1;
	}

	/* 実行部分 */
	j=1;
	while(j <= sqrt(N)){
		if(targetArray[j] == 1){
			for(k=j+2; k <= N; k++){
				if(k%(j+1) == 0){
					targetArray[k-1]=0;
				}
			}
		}
		j++;
	}

	/* 表示部 */
	printf("%d 以下に含まれる素数: \n", N);
	for(l=1; l < N; l++){
		if(targetArray[l] == 1){
			printf("%d ", l+1);
		}
	}

	return 0;
}

上のコードを「prime_sieve.c」とでも名前を付けて保存しましょう。(sieveとは「ふるい」という意味です)
「gcc -o prime_sieve prime_sieve.c」でコンパイル、「prime_sieve.exe」で実行できます。
実行した画面をFIg. 1に示します。

Fig. 1 素数を求めるプログラム「prime_sieve.c」の実行画面

無事に実行ができたらソースコード内の4行目の「define N 200」の
200の部分を違う数字に変えてみて、きちんと素数を求められているか確認してみましょう。

前回との大きな違いに配列を使っていることが挙げられます。
配列は同じ型のデータをまとめて扱うことができるものです。

例えば、「30人分の成績」を扱うときに、逐一変数を定義するのは大変なので、
int seiseki[30];と定義してあげれば、全てint型で
seiseki[0], seiseki[1], seiseki[2], …, seiseki[28], seiseki[29]と30個の変数が一気に定義できます。

また今回はそういった扱いをしませんでしたが、配列というのは数学的に言えば「ベクトル」や「行列」そのものであり、
工学的に言えばそれらは「データ」や「操作」を意味します。(ここら辺はとっても楽しい話ですが、またの機会に…)

変数や配列を定義するときに、データと格納する場所が確保されるイメージを持っていると理解しやすいです。
また配列のリスト番号は0スタートなので、たとえば4個分定義する場合のリスト番号は0, 1, 2, 3になります。(Fig. 2, 3)

Fig. 2 変数を扱うときのイメージ
Fig. 3 配列を扱うときのイメージ

今回のプログラムではリスト番号(インデックス)と、実際に対象としている数字がずれているので、
かなりわかりにくくなってしまいました。探索リストであるtargetArrayの扱いをFig. 4に示します。

Fig. 4 本プログラムにおけるtargetArrayの扱い

さて、プログラムの中身についてです。
「3 エラトステネスの篩」内のリストに沿って説明していきます。

1 数字を指定する部分 =4行目

かつてmain関数が真っ先に呼ばれる、という旨の説明をしたことがありますが、
実はincludeやdefineはその前に呼ばれます。

ここでは「N」というものが出てきたら「200」として扱ってくださいという宣言をしています。
本来、Cにおける配列のサイズは変数で定義できません。
(mallocなどで可変長にする方法はあります。)
しかし予め「Nは200」と知っているので7行目のような使い方ができます。

2 2~Nまでの数字列を探索リストとする =7、17行目

探索リストの仕様はFig. 4に示したとおりです。(7行目で定義)
しかし1は素数ではないので11行目で「0」を代入しています。
また「2から」探索リストなので探索開始時のインデックス(j)を1にしています。(17行目)

3 探索リストに残っている先頭の数字は素数 =13行目

何もなければ(ふるいによって落とされなければ)素数と判断するので、
初期化のときに2~Nまで1を代入(=素数であるという判定)をします。

4 先頭の数字の倍数を探索リストから除外 =19~25行目

対象としている先頭の数のインデックスjにあたります。
したがって対象としている先頭の数は(j+1)です。

対象としている先頭の数の次の数は(j+2)で、そこからNまで、
対象としている先頭の数(j+1)の倍数か(つまり(j+1)で割りきれるか)判断して、
倍数(余りが0なら)ならば0を代入しています。

19行目のif文で対象としている数字が0なら、無視される=探索されないので
実質的に探索リストから除外されたことになります。
(もしわかりにくい場合は実際に数字をいれて考えてみてください。)

5 探索を先頭の数が√Nを超えるまで繰り返す =18、26行目

18行目のwhile文はカッコ()内の条件を満たしている間はブロック{}内の処理を繰り返します。
ブロック内には3、4の手順が記述されています。

sqrt関数は2行目でincludeしたmath.hで用意されている関数で、
(正の)平方根を計算してくれます。

6 残ったものが素数

探索リスト内で1になっているところが素数になります。(0は除外の意味にしていました。)
したがって32行目でリスト内の1になっている時にだけ、printfをします。
またリストのインデックスは0スタートなので33行目でインデックスに1を足して表示しています。

5 まとめ

  • アルゴリズムについて説明
  • アルゴリズムのひとつであるエラトステネスの篩の実装
  • 配列は便利

構造体やポインタを扱わずしてC言語入門を終えるのは名残惜しいですが、
他の言語をやるステップアップになりやすいか?
と考えると微妙なラインだと思うので、後回しにします。

次の初心者向け解説は別の言語にする予定です。広く浅く。

「C言語入門 5 (素数を扱う 2)」への1件のフィードバック

  1. 心はすべて数学である

    ≪…アルゴリズムのひとつであるエラトステネスの篩…≫との事は、素数を創生するとの観方で捉えると
    『身体がする数学』と生る。
    これから、『幻のマスキングテープ』できるらしい・・・
    『身体がする数学』の自然数は、
    [絵本]『もろはのつるぎ」で・・・

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です