ユークリッドの互除法

アルゴリズムの実装

ではまず、ユークリッドの互除法から説明していきましょう。C言語でユークリッドの互除法を実装すると、いかのようになります。

#include <stdio.h>

void main(){
	int m , n, d;
	printf("一つ目の数:");
	scanf("%d", &m);
	printf("二つ目の数:");
	scanf("%d", &n);
	//	m < nであれば、mとnを入れ替える
	if (m > n){
		int tmp = m;
		m = n;
		n = tmp;
	}
	do{
		d = m % n;
		m = n;
		n = d;
	} while (d != 0);
	printf("二つの数の最大公約数は最大公約数は%dです。¥n", m);
}

プログラムを実行すると、コンソールから、二回せいすうのあたいを入力するように求めてきます。入力すると、その数値の最大公約数が表示されます。

実行結果
一つ目の数:36
二つ目の数:48
二つの数の最大公約数は最大公約数は48です。

エラトステネスのふるい

アルゴリズムの実装

続いて、エラトステネスふるいをC言語で実装したものを紹介します。以下のサンプルは、100までの素数を算出するものです。定数Nの値を変えれば、その数までの素数を求めることができます。

#include <stdio.h>

#define N	100

void main(){
	//	Nまでの数の素数を表示する。
	int i,m,n;
	int data[N + 1], result[N + 1];
	//	配列の要素に1を入れる。
	for (i = 0; i < N+1; i++){
		data[i] = 1;
	}
	//	0と1は、最初から除外する
	data[0] = 0;
	data[1] = 0;
	m = 2;
	n = 0;
	do{
		//	素数の倍数をリストから削除する
		for (i = 2 * m; i < N + 1; i+=m){
			data[i] = 0;
		}
		//	結果を格納
		result[n] = m;
		n++;
		//	次の素数候補を見つける
		do{
			m++;
		}while (data[m] == 0 && m < N + 1);
	} while (m < N + 1);
	//	結果の出力
	for (i = 0; i < n; i++){
		//	10行ごとに改行
		printf("%3d ", result[i]);
		if ((i+1) % 10 == 0){
			printf("¥n");
		}
	}
	printf("¥n");
}

プログラムを実行すると、コンソールから、二回せいすうのあたいを入力するように求めてきます。入力すると、その数値の最大公約数が表示されます。

実行結果
  2   3   5   7  11  13  17  19  23  29
31  37  41  43  47  53  59  61  67  71
73  79  83  89  97