２つの数の最大公約数を求める

元の記事とは関係ないけどおまけ

ループその１

何にもわからなかったら、まずは素朴に書いてみるといいでしょう

int	gcd( int	a, int	b ){
	int	result = 1;
	int	halfof_min_ab = (( a < b ) ? a : b ) / 2;
	int	m = 2;
	while( m <= halfof_min_ab ){
		if( !( a % m ) && !( b % m )){
			result = m;
		}
		++m;
	}
	return	result;
}

int	lcm( int	a, int	b ){
	return	( a * b ) / gcd( a, b );
}

void	print_gcd_lcm( int	a, int	b ){
	debug_printf( "%d と %d の最大公約数は %d, 最小公倍数は %d\n", a, b, gcd( a, b ), lcm( a, b ));
}

int	main(){
	print_gcd_lcm( 21, 35 );
	print_gcd_lcm( 35, 21 );
	return	0;
}

ループその２

ユークリッドの互除法

int	gcd( int	a, int	b ){
	while( b ){
		int	m = a % b;
		a = b;
		b = m;
	}
	return	a;
}

int	lcm( int	a, int	b ){
	return	( a * b ) / gcd( a, b );
}

void	print_gcd_lcm( int	a, int	b ){
	debug_printf( "%d と %d の最大公約数は %d, 最小公倍数は %d\n", a, b, gcd( a, b ), lcm( a, b ));
}

int	main(){
	print_gcd_lcm( 21, 35 );
	print_gcd_lcm( 35, 21 );
	return	0;
}

再帰

ループは再帰にできる

int	gcd( int	a, int	b ){
	return	!b ? a : gcd( b, a % b );
}

int	lcm( int	a, int	b ){
	return	( a * b ) / gcd( a, b );
}

void	print_gcd_lcm( int	a, int	b ){
	debug_printf( "%d と %d の最大公約数は %d, 最小公倍数は %d\n", a, b, gcd( a, b ), lcm( a, b ));
}

int	main(){
	print_gcd_lcm( 21, 35 );
	print_gcd_lcm( 35, 21 );
	return	0;
}

テンプレート

再帰条件をコンパイル時に決定できるならテンプレートにできる

template<int a,int b> struct gcd_helper_t {
	static const int	first = b;
	static const int	second = a % b;
};
template<int a,int b> struct gcd_t {
	static const int	value = gcd_t<gcd_helper_t<a,b>::first,gcd_helper_t<a,b>::second>::value;
};
template<int a> struct gcd_t<a,0> {
	static const int	value = a;
};
template<int a,int b> struct lcm_t {
	static const int	value = ( a * b ) / gcd_t<a,b>::value;
};
template<int a,int b> void	print_gcd_lcm(){
	debug_printf( "%d と %d の最大公約数は %d, 最小公倍数は %d\n", a, b, gcd_t<a,b>::value, lcm_t<a,b>::value );
}

int	main(){
	print_gcd_lcm<21,35>();
	print_gcd_lcm<35,21>();
	return	0;
}