求两个正整数的最大公约数 - 算法与代码示例

最大公约数即为两个数的公共因子中最大的那个数。首先找到两个数中较小的那个数，然后从较小的数开始递减，找到两个数都能整除的最大的那个数即为最大公约数。\n\n具体算法如下：\n\n1. 读取输入的两个数 m 和 n。\n2. 将 m 和 n 中的较小值赋给变量 min_num。\n3. 从 min_num 开始递减，判断是否能同时整除 m 和 n，如果能整除，则找到最大公约数，输出该数并结束。\n4. 如果一直没有找到能同时整除 m 和 n 的数，则最大公约数为 1，输出 1。\n\n代码示例：\n\npython\nm, n = map(int, input().split())\n\nmin_num = min(m, n)\n\nfor i in range(min_num, 0, -1):\n if m % i == 0 and n % i == 0:\n print(i)\n break\n\nif i == 1:\n print(1)\n\n\n时间复杂度分析：\n\n最坏情况下，需要遍历的次数为 min(m, n) 次，所以时间复杂度为 O(min(m, n))。