公約数を全て表示するプログラムです

[KTN19]

最大公約数を計算する関数（教科書p.188 リスト5.18参照） int gcd( int x, int y) を利用して，2つの自然数 x, y に対し，その公約数をすべて求め，int 型配列 c に格納する関数 void cd(int x, int y, int c[]) を作成せよ．
さらに，main 関数で 2つの自然数 x，y を入力させ，関数 cd を呼び出し，配列 c に格納されたすべての公約数を表示するプログラムを作成
という問題なのですが、この問題にめちゃくちゃ悩んでいて、どうにも一人ではできそうにないので、どうかご教授願います。

コード:

#include <stdio.h>
#include<math.h>
#define N 1000

int gcd( int x, int y );
void cd( int x, int y, int c[] );

int main( void )
{
int x, y, i;
int d[ N ];

printf( "自然数を大きい方を入力>>>" );
scanf( "%d", &x );
printf( "自然数を小さい方を入力>>>" );
scanf( "%d", &y );

cd( x, y, d );


return 0;
}

int gcd( int x, int y )
{
int a, b ,z;

y = 1;
for( a = 2; a <= x; a++ )
{
if( ( x % a == 0 ) && ( x % b == 0 ) )
{
y = x;
}
z = y;
}
return z;
}
void cd( int x, int y, int c[] )
{
int i, z, a, b;

for( i = 0; i < N; i++ )
{
c[ i ] = ( z = gcd( a, b ) );
if( y > 0 ){
printf( "a = %d, b = %dの時,公約数は %d ¥n", x, y, c[ i ] );
break;
}
else{
break;
}
}
}

[みけCAT]

とりあえず気になったのですが、

最大公約数を計算する関数（教科書p.188 リスト5.18参照） int gcd( int x, int y) を利用して，

int gcd( int x, int y )
{
int a, b ,z;

y = 1;
for( a = 2; a <= x; a++ )
{
if( ( x % a == 0 ) && ( x % b == 0 ) )
{
y = x;
}
z = y;
}
return z;
}

あなたの教科書には本当にこんなひどいプログラムが載っているのですか？

• 入力yを全く使わずに破壊している
• 未初期化で不定の値が入っているbが使用されている
• xが1以下の時、未初期化で不定の値であるzを返している
• xとしてINT_MAXが与えられた時、無限ループになる可能性がある(符号付き整数のオーバーフローは未定義動作)

こんな謎処理で最大公約数が計算できるわけがないですね。

[みけCAT]

とりあえず愚直な方法で求めるコードに修正してみました。
関数gcdは呼び出しても有効活用できなそうなので、0や1を作るのに利用してみました。

コード:

#include <stdio.h>
#include <stdlib.h>
#define N 1000

int gcd( int x, int y );
void cd( int x, int y, int c[] );

int main( void )
{
	int x, y, i;
	int c[ N ];
	for (i = 0; i < N; i++) c[i] = -1; /* 配列を初期化する */
	
	printf( "自然数を大きい方を入力>>>" );
	if (scanf( "%d", &x ) != 1 || x < 0)
	{
		puts("入力エラー");
		return 1;
	}
	printf( "自然数を小さい方を入力>>>" );
	if (scanf( "%d", &y ) != 1 || y < 0 || x <= y)
	{
		puts("入力エラー");
		return 1;
	}
	
	cd( x, y, c );

	for (i = 0; c[i] >= 0; i++) {
		printf("%d\n", c[i]);
	}

	return 0;
}

int gcd( int x, int y )
{
	int a, b ,z;
	
	y = 1;
	for( a = 2; a <= x; a++ )
	{
		if( ( x % a == 0 ) && ( x % b == 0 ) )
		{
			y = x;
		}
		z = y;
	}
	return z;
}

void cd( int x, int y, int c[] )
{
	int i, n = !gcd;
	
	for( i = !!gcd; i <= x && i <= y; i++ )
	{
		if (x % i == !gcd && y % i == !gcd)
		{
			c[ n++ ] = i;
			if (n >= N)
			{
				puts("エラー : 約数が多すぎます");
				exit(1);
			}
		}
		if (i == x || i == y) break; /* オーバーフロー回避 */
	}
}

[KTN19]

お早い返信とアドバイスをありがとうございます。

書いたプログラムについてですが、このサイトを見かける前に悩み、頭を通さずに書いたものでした。汗

[みけCAT]

真面目に書いてみました。
約数の順番はバラバラになるので、必要ならソートの処理を追加してください。

コード:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define N 1000

int gcd( int x, int y );
void cd( int x, int y, int c[] );

int main( void )
{
	int x, y, i;
	int c[ N ];
	for (i = 0; i < N; i++) c[i] = -1; /* 配列を初期化する */
	
	printf( "自然数を大きい方を入力>>>" );
	if(scanf( "%d", &x ) != 1 || x < 0)
	{
		puts("入力エラー");
		return 1;
	}
	printf( "自然数を小さい方を入力>>>" );
	if(scanf( "%d", &y ) != 1 || y < 0 || x <= y)
	{
		puts("入力エラー");
		return 1;
	}
	
	cd( x, y, c );

	for(i = 0; c[i] >= 0; i++) {
		printf("%d\n", c[i]);
	}

	return 0;
}

int gcd( int x, int y )
{
	int a, b ,z;
	
	y = 1;
	for( a = 2; a <= x; a++ )
	{
		if( ( x % a == 0 ) && ( x % b == 0 ) )
		{
			y = x;
		}
		z = y;
	}
	return z;
}

void cd( int x, int y, int c[] )
{
	struct node {
		int val;
		int num;
		struct node *next;
	};
	struct stack {
		struct node *node;
		int current_value;
		int current_count;
		struct stack *next;
	};

	int n, n1;
	int i;
	int index;
	struct node *head, **tail;
	struct stack *stack_top, *stack_pool;
	if(x <= 0 || y <= 0) return;

	/* xとyの最大公約数を求める */
	n = x;
	n1 = y;
	while(n1 > !gcd)
	{
		int n2 = n % n1;
		n = n1;
		n1 = n2;
	}

	/* 求めた最大公約数を素因数分解する */
	head = NULL;
	tail = &head;
	for(i = !!gcd + !!gcd; i <= INT_MAX / i && i * i <= n; i++)
	{
		if(n % i == !gcd)
		{
			/* 割り切れたら */
			int count = !gcd;
			/* 割り切れなくなるまで割る */
			while(n % i == !gcd)
			{
				n /= i;
				count++;
			}
			/* 割った回数と割る数を格納する */
			*tail = malloc(sizeof(struct node));
			if(*tail == NULL)
			{
				perror("malloc");
				exit(1);
			}
			(*tail)->val = i;
			(*tail)->num = count;
			(*tail)->next = NULL;
			tail = &(*tail)->next;
		}
	}
	if(n > !!gcd)
	{
		/* 割り切れずに残った数を格納する */
		*tail = malloc(sizeof(struct node));
		if(*tail == NULL)
		{
			perror("malloc");
			exit(1);
		}
		(*tail)->val = n;
		(*tail)->num = !!gcd;
		(*tail)->next = NULL;
		tail = &(*tail)->next;
	}

	/* 素因数分解の結果を用いて、最大公約数の約数を全て求める */
	stack_pool = NULL;
	stack_top = malloc(sizeof(struct stack));
	stack_top->node = head;
	stack_top->current_value = !!gcd;
	stack_top->current_count = !gcd;
	stack_top->next = NULL;
	index = !gcd;
	while(stack_top != NULL)
	{
		if(stack_top->node == NULL || stack_top->current_count > stack_top->node->num)
		{
			if (stack_top->node == NULL) {
				/* 最後まで行ったので、約数を格納する */
				c[ index++ ] = stack_top->current_value;
				if (index >= N)
				{
					puts("エラー : 約数が多すぎます");
					exit(1);
				}
			}
			/* この素因数の処理は終わり */
			struct stack *node_to_del = stack_top;
			stack_top = stack_top->next;
			node_to_del->next = stack_pool;
			stack_pool = node_to_del;
		}
		else{
			/* この素因数の処理を行う */
			struct stack *next_node;
			if(stack_pool != NULL)
			{
				/* 既に確保したノードがあるので、それを使う */
				next_node = stack_pool;
				stack_pool = stack_pool->next;
			}
			else{
				/* 新たにノードを確保する */
				next_node = malloc(sizeof(struct stack));
				if(next_node == NULL)
				{
					perror("malloc");
					exit(1);
				}
			}
			/* 次の処理の情報を格納する */
			next_node->node = stack_top->node->next;
			next_node->current_value = stack_top->current_value;
			next_node->current_count = !gcd;
			next_node->next = stack_top;
			/* 今の処理の情報を更新する */
			stack_top->current_count++;
			if(stack_top->current_count <= stack_top->node->num)
			{
				stack_top->current_value *= stack_top->node->val;
			}
			/* 次の処理に移る */
			stack_top = next_node;
		}
	}
	/* 後片付けを行う */
	while(head != NULL)
	{
		struct node *next = head->next;
		free(head);
		head = next;
	}
	while(stack_pool != NULL)
	{
		struct stack *next = stack_pool->next;
		free(stack_pool);
		stack_pool = next;
	}
}

[KTN19]

すみません。真面目に書かれすぎて頭がパンクしました。笑
まだ、習っていない範囲のもので参考にしづらいです。苦笑
失礼極まりないですが、教科書にあったもの確認をお願いしていいですか？

コード:

#include <stdio.h>
#include<math.h>
#define N 1000

int gcd( int x, int y );
void cd( int x, int y, int c[] );

int main( void )
{
	int x, y, i;
	int c[ N ];
	for( i = 0; i < N; i++ ) c[ i ] = -1;
	
	/*　 入力する数は2400,2040です　*/
	printf( "自然数を大きい方を入力>>>" );
	scanf( "%d", &x ); 
	printf( "自然数を小さい方を入力>>>" );
	scanf( "%d", &y );
	
	cd( x, y, c );
	for( i = 0; c[ i ] >= 0; i ++ ){
		printf( "%d ¥n", c[ i ] );
	}

	
	return 0;
}

int gcd( int x, int y )
{
	int z;
	
	while( ( z = x % y ) != 0 )
	{
		x = y;
		y = z;
	}
	
	return y;
}
void cd( int x, int y, int c[] )
{
	int i, z;
	
	for( i = 0; i <= x && i <= y; i++ )
	{
		
		if( z > 0 ){
			c[ z++ ] = i;
			printf( "a = %d, b = %dの時,公約数は %d ¥n", x, y, c[ i ] );
		}
		else{
			break;
		}
	}
}
「/code]

[みけCAT]

int gcd( int x, int y )
{
int z;

while( ( z = x % y ) != 0 )
{
x = y;
y = z;
}

return y;
}

正しそうですね。

void cd( int x, int y, int c[] )
{
int i, z;

for( i = 0; i <= x && i <= y; i++ )
{

if( z > 0 ){
c[ z++ ] = i;
printf( "a = %d, b = %dの時,公約数は %d ¥n", x, y, c[ i ] );
}
else{
break;
}
}
}

未初期化で不定の値が入ったzが比較演算や添字で用いられているため、間違っています。
他にもおかしな所がありそうですね。

[かずま]

最大公約数を計算する関数（教科書p.188 リスト5.18参照） int gcd( int x, int y) を利用して，2つの自然数 x, y に対し，その公約数をすべて求め，int 型配列 c に格納する関数 void cd(int x, int y, int c[]) を作成せよ．

公約数は、最大公約数の約数であるということを利用するだけじゃないの？

コード:

void cd(int x, int y, int c[])
{
    int g = gcd(x, y), i = 0, d;

    for (d = 1; d <= g; d++)
        if (g % d == 0)
            c[i++] = d;
}

i が N 以上になる場合のエラー処理が必要になるでしょうが、....

[KTN19]

かずまさん、みけCATさん。
大変感謝します！！
一先ず課題は上手くできました！！m(_ _ )m
また機会があれば、ご教授ください！！

コード:

#include <stdio.h>
#include<math.h>
#define N 1000

int gcd( int x, int y );
void cd( int x, int y, int c[] );

int main( void )
{
	int x, y, i;
	int c[ N ];
	for( i = 0; i < N; i++ ) c[ i ] = -1;
	
	printf( "自然数を大きい方を入力>>>" );
	scanf( "%d", &x ); 
	printf( "自然数を小さい方を入力>>>" );
	scanf( "%d", &y );
	
	cd( x, y, c );
	for( i = 0; c[ i ] >= 0; i ++ ){
		printf( "%d ¥n", c[ i ] );
	}

	
	return 0;
}

int gcd( int x, int y )
{
	int z;
	
	while( ( z = x % y ) != 0 ){
		x = y;
		y = z;
	}
	
	return y;
}
void cd( int x, int y, int c[] )
{
	int i, z = gcd( x, y ), j;
	
	i = 0;
	for( j = 1; j <= z; j++){		
		if( z % j == 0 ){	
			c[ i++ ] = j;
		}
	}
}