2つの自然数の最大公約数と最小公倍数を求める
最大公約数は(ユークリッドの互除法 - Wikipedia)によって求め、
最小公倍数は、
「正整数a、bに対して、
aとbの最大公約数 gcd(a、b) と最小公倍数 lcm(a、b) との間には
gcd(a、b)・lcm(a、b) = ab
という関係がある。」(最小公倍数 - Wikipedia)
を利用して求める
# include <stdio.h> //プロトタイプ宣言 int gcd(int x, int y); //最大公約数を求める関数 int lcm(int x, int y); //最小公倍数を求める関数 int main(void) { int x, y, temp; int gcd_n, lcm_n; do { printf("一つ目の自然数を入力してください > "); scanf("%d", &x); printf("もうひとつの自然数を入力してください > "); scanf("%d", &y); } while((x != y) && (x < 0) && (y < 0)); if(x < y) { temp = x; x = y; y = temp; } gcd_n = gcd(x, y); lcm_n = lcm(x, y); printf("%dと%dの最大公約数は%d, 最小公倍数は%dです\n", x, y, gcd_n, lcm_n); return 0; } int gcd(int x, int y) { int r; while(x%y != 0) { r = x%y; x = y; y = r; } return y; } int lcm(int x, int y) { int r; r = (x*y)/gcd(x, y); return r; }
実行結果
一つ目の自然数を入力してください > 27
もうひとつの自然数を入力してください > 36
36と27の最大公約数は9、最小公倍数は108です