文章目录

• 最大公约数
• • 概念
  • 求解方法
  • • 1）辗转相除法
    • • 简便算法 ：
    • 2)相减法
    • • 原理：
      • 代码实现
    • 3)穷举法 （用循环）
    • • 思路：
      • 代码实现：
• 最小公倍数
• • 概念

最大公约数

概念

两个或多个整数共有约数中最大的一个

求解方法

1）辗转相除法

两整数a和b：

① a%b得余数c；

② 若c=0，则b即为两数的最大公约数；

③ 若c≠0，则a=b，b=c，再回去执行①；

例如，求36和15的最大公约数过程为：36÷15=2......615÷6 = 1......36÷3 = 2 ......0因此，36和15的最大公约数是 3；

辗转相除法 求 最大公约数

#includeint main(){     int a, b,c,m,n;     scanf("%d%d", &a, &b);      m = a,n = b; while(b!=0)  //余数不为0时，继续相除，直到余数为0         {   c=a%b;    a=b;     b=c;}    printf("最大公约数为:%d", a);  

简便算法 ：

int gcd(int a,int b){    return b == 0?a:gcd(b,a%b); }

2)相减法

原理：

整数a、b：
① 若a>b，则a=a-b；
② 若a<b，则b=b-a；
③ 若a=b，则a（或b）即为两数的最大公约数；
④ 若a≠b，则再回去执行①；

例如：求36和15的最大公约数过程为：36 - 15 = 21     （21>15)  21 - 15 = 6(15>6)15 - 6 = 9 (9>6)9 - 3 = 3  (6>3)6 - 3 = 3  (3 =3)因此，3即为最大公约数

代码实现

 相减法求最大公约数 #include int main ( ) {int m, n, a, b, c;     printf("Input two integer numbers:");    scanf ("%d,%d", &a, &b);  m=a; n=b;      while ( a!=b)    {      if (a>b)a=a-b;else     b=b-a;      }    printf("最大公约数r:%d", a); return 0; }

3)穷举法 （用循环）

思路：

整数a、b
①int i= a(或b)
②若a，b能同时被i整除，则i即为最大公约数。此时，一次循环结束。
③ i–，再回去执行②

代码实现：

/*穷举法 求 最大公约数*/# includeint main(){   int a,b,t = 0;   scanf("%d %d",&a,&b);   for(int i=1; i<=a&&i<=b; i++)    {if(a%i == 0 && b%i == 0){ t = i;}   }   printf("最大公约数为%d\n",t);   return 0;}

最小公倍数

概念

数论中的一种概念，两个整数公有的倍数成为他们的公倍数，其中一个最小的公倍数是他们的最小公倍数，同样地，若干个整数公有的倍数中最小的正整数称为它们的最小公倍数。

故 ：最小公倍数 = 两数乘积 / 最大公约数；

故，用上面的方法求出最大公约数以后，直接套用 最小公倍数 = 两数乘积 / 最大公约数 的公式即可。

特别地，

若要用穷举法 单独求最小公倍数 而 不求最大公约数，可用如下思路：

① i= a(或b)② 若a，b能同时被i整除，则i即为最大公约数。此次循环结束。③ i--，再回去执行②

代码实现：

#includeint main(){    int a,b,i;    scanf("%d%d",&a,&b);    for (i= a; ; i++ )    { if ( i % a == 0 && i % b ==0 ) {     break; }    }    printf("最小公倍数为%d", i );    return 0;}