习题4-7 最大公约数和最小公倍数 (15 分)

题目描述

本题要求两个给定正整数的最大公约数和最小公倍数。

输入格式

输入在一行中给出两个正整数M和N（≤1000）。

输出格式

在一行中顺序输出M和N的最大公约数和最小公倍数，两数字间以1空格分隔。

输入样例

511 292

输出样例

73 2044

参考代码

#include<stdio.h>
int gcd(int a, int b);
int lcm(int a, int b);
int main() {
	int m, n, result_gcd, result_lcm;
	scanf("%d %d", &m, &n);
	result_gcd = gcd(m, n);
	result_lcm = lcm(m, n);
	printf("%d %d\n", result_gcd, result_lcm);
	return 0;
}
int gcd(int a, int b) {
	int temp;
	if (a < b) {
		//交换两个数，使大数放在a上
		temp = a;
		a = b;
		b = temp;
	}
	while (b != 0) {
		//利用辗除法，直到b为0为止
		temp = a % b;
		a = b;
		b = temp;
	}
	return a;
}
int lcm(int a, int b) {
	int temp_lcm;
	temp_lcm = a * b / gcd(a, b);//最小公倍数等于两数之积除以其最大公约数
	return temp_lcm;
}