紅茶は無糖

プログラミング勉強中 その他雑多なことも記録

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です