题目描述

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

题目要求

• 输入格式：输入在两行中分别输入正整数x和y
• 输出格式：在一行中输出最大公约数和最小公倍数的值
• 例如：输入100 1520 输出20 7600

题目解析

（1）几个整数中公有的约数，叫做这几个数的公约数；其中最大的一个，叫做这几个数的最大公约数

例如：求24和60的最大公约数，先分解质因数，得24=2×2×2×3，60=2×2×3×5，24与60的全部公有的质因数是2、2、3，它们的积是2×2×3=12，所以，（24，60）=12。

（2）几个自然数公有的倍数，叫做这几个数的公倍数，其中最小的一个自然数，叫做这几个数的最小公倍数

例如：求6和15的最小公倍数。先分解质因数，得6=2×3，15=3×5，6和15的全部公有的质因数是3，6独有质因数是2，15独有的质因数是5，2×3×5=30，30里面包含6的全部质因数2和3，还包含了15的全部质因数3和5，且30是6和15的公倍数中最小的一个，所以[6，15]=30。

思路

（1）最大公约数
假设最大公约数为a，2个数为x和y，则x一定能够整除a，且y也能整除a，如24和60的最大公约数为24
求最大公约数时，最大公约数的范围是[1,最小值]，故可以用x和y对从1开始的整数取余，若余数为0，则说明可以整除，保存该约数，直到取到最大约数，即为最大公约数

（2）最小公倍数

假设最小公倍数为b，2个数为x和y，作为x和y的公倍数，则b一定能够整除x和y，如6和15的最小公倍数为30
求最小公倍数时，最小公倍数的范围是[x和y的最大值，正无穷]，故从x和y的最大值开始，对x和y取余，当第一个余数为0时，则此时的数即为x和y的最小公倍数

运行结果：

文章知识点与官方知识档案匹配，可进一步学习相关知识Python入门技能树首页概览214401 人正在系统学习中