c语言之求最大公约数（辗转相除法）和最小公倍数（3种方法）

1、最大公约数

例如：给定两个数20，40
他们的最大公约书就是20；
15，10
它们最大公约数就是5。
这里我们可以用辗转相除法来进行计算：
首先何为辗转相除法，顾名思义就是两个数一直相互除，例如15和9两个数进行辗转相除，15%9=6，然后就是9%6=3，然后就是6%3=0最后得到0为止，3就为最大公约数。
最后我们按照逻辑进行程序设计即可，先判断输入两个数的大小，保证被除数为较大值，被除数为较小值。然后开始辗转相除，利用while循环。最后b值为我们要找的值。

#inlude <stdio.h>int main(){int a, b = 0;int r = 0;while (scanf("%d %d", &a, &b) != EOF)//多值输入{if (a < b){r = a;a = b;b = r;} while (a % b != 0){ r = a % b; a = b; b = r;}printf("%d\n", b);}return 0;}

2、最小公倍数

例如：给定两个数12和4，最小公倍数就是12.
1、求解最小公倍数最直接的方法就是先比较两个数的大小，将较大的数拿出来，逐渐累加，直到这个数能够将两个数同时除清

#include int main() { int a = 0; int b = 0;scanf("%d %d", &a, &b); //求出a和b的较大值 int m = a>b?a:b; while(1){ if(m%a==0 && m%b==0)break; m++;}printf("%d\n", m);return 0;}

这种方法简单直接，但是这个的时间复杂度比较高，计算时间长，因此有些题目就不太支持这种方法。
2、假设给定两个数a和b，他们的最大公约数为c，我们可以知道最小公倍数等于（a*b）/c。
因此我们就可以利用辗转相除法先算除最大公约数，在利用公式算出最小公倍数。这样的算法的时间复杂度就变很低了

#include int main(){ int a, b = 0; int r = 0; while (scanf("%d %d", &a, &b) != EOF) { int n = a * b;; if (a < b) { r = a; a = b; b = r; } while (a % b != 0) { r = a % b; a = b; b = r; } printf("%d\n", n / b); } return 0;}

3、还有一种方法就是，先比较出两个数的大小，然后给较大值不断乘上i，i进行累加，这样效果也会比第一种快的多。

#include int main(){ long long a = 0; long long b = 0; long long r =0; scanf("%lld %lld", &a, &b);//求出a和b的较大值 if (a < b) {r = a;a = b;b = r;} long long i = 1; while (i * a % b != 0) { i++; }printf("%lld\n", i * a);return 0;}

需要注意的一点就是这里用long long类型就是防止有一些较大的数，超过int类型的最大范围，例如牛客网上显示有一部分用例没有通过，这里就需要根据题目要求来选择类型。