最大公约数和最小公倍数 分数 10 作者 张彤彧 单位 浙江大学 本题要求两个给定正整数的最大公约数和最小公倍数。 输入格式: 输入在一行中给出两个正整数M和N（≤1000）。 输出格式: 在一行中顺序输出M和N的最大公约数和

最小公倍数。
最大公约数和最小公倍数是数学中常见的概念，其中最大公约数指的是两个数中最大的公因数，最小公倍数指的是两个数中最小的公倍数。求最大公约数和最小公倍数的方法有多种，其中辗转相除法和质因数分解法是比较常用的方法。
1.辗转相除法：假设a、b是两个正整数，a>b，用a除以b，得到余数c，若c=0，则b就是a和b的最大公约数；否则，用b除以c，得到余数d，若d=0，则c就是a和b的最大公约数；否则，继续用c除以d，直到余数为0为止，此时最后一个非零余数就是a和b的最大公约数。最小公倍数可以用两个数的乘积除以它们的最大公约数来求得。
2.质因数分解法：将两个数分别分解质因数，然后将它们的公共质因数乘起来，得到的积就是它们的最大公约数；它们的所有质因数乘起来，再除以它们的最大公约数，得到的商就是它们的最小公倍数。