求最大公约数以及最小公倍数

求最大公约数以及最小公倍数

整体代码

#include <stdio.h>  
#include <ctype.h>  
#include <math.h>  
int main() {  
  int m,n;  
  int c;  
  
  scanf("%d%d",&m,&n);  
  int a=m;  
  int b=n;  
  
  /*辗转相除法 (欧几里得算法)  
  首先将两个数进行模运算，即a%b  
  ① 当a能被b整除时即 a%b == θ，直接返回 b，b就是最大公约数。  
  例如，a=12，b=6，a%b=0，b=6就是这两个数的最大公约数。  
  ② 当a不能被b整除时 a%b != 0，则进行辗转相除。  
  用第三个变量来接收 a%b，即 c = a%b，用 a 来接收 b的值，用 b 来接收 c 的值。③ 重复上述①和②*/  
  if (m%n==0) {  
    printf("%d",n);  
  }  
  else {  
    while (m%n!=0) {  
      c=m%n;  
      m=n;  
      n=c;  
    }  
    printf("%d ",n);  
  }  
  
  /*求两个数的最小公倍数  
  关于最小公倍数与最大公约数，有这样的定理：最小公倍数×最大公约数=两数的乘积。  
  即：最小公倍数=两数的乘积÷最大公约数*/  
  int t;  
  t=a*b/n;  
  printf("%d",t);  
  
  return 0;  
}

最大共公约数

常用方法

• “辗转相除法”，又名欧几里得算法 ### 如下
• 设两数为a和b(a>b)，用a除以b，得a÷b=q……….r，若r=0，则最大公约数为b；若r≠0,则再用 b÷r，得b÷r=q……..r'，若r'=0，则最大公约数为r'，若r'≠0，则继续用r÷r'………..直到能够整 除为止，此时的除数即为最大公约数。 ### 例如
• a=99，b=18。a÷b=99÷18=5.………..9不能整除，则继续b÷r=18÷9=2可以整除，则此时的 除数9即为a和b两数的最大公约数。 ### 代码

- int main() {  
  int m,n;  
  int c;  
  
  scanf("%d%d",&m,&n);  
  int a=m;  
  int b=n;  
  
  /*辗转相除法 (欧几里得算法)  
  首先将两个数进行模运算，即a%b  
  ① 当a能被b整除时即 a%b == θ，直接返回 b，b就是最大公约数。  
  例如，a=12，b=6，a%b=0，b=6就是这两个数的最大公约数。  
  ② 当a不能被b整除时 a%b != 0，则进行辗转相除。  
  用第三个变量来接收 a%b，即 c = a%b，用 a 来接收 b的值，用 b 来接收 c 的值。③ 重复上述①和②*/  
  if (m%n==0) {  
    printf("%d",n);  
  }  
  else {  
    while (m%n!=0) {  
      c=m%n;  
      m=n;  
      n=c;  
    }  
    printf("%d ",n);  
  }

最小公倍数

方法

• 关于最小公倍数与最大公约数，有这样的定理：最小公倍数×最大公约数=两数的乘积。
• 即：最小公倍数=两数的乘积÷最大公约数

代码

/*求两个数的最小公倍数  
关于最小公倍数与最大公约数，有这样的定理：最小公倍数×最大公约数=两数的乘积。  
即：最小公倍数=两数的乘积÷最大公约数*/  
int t;  
t=a*b/n;  
printf("%d",t);