求解最大公约数----最小公倍数

简介: 最大公因数和最小公倍数之间的性质:两个自然数的乘积等于这两个自然数的最大公约数和最小公倍数的乘积。最小公倍数的计算要把三个数的公有质因数和独有质因数都要找全,最后除到两两互质为止。

最小公倍数与最大公约数


  最小公倍数的性质:公倍数(common multiple)指在两个或两个以上的自然数中, 如果它们
  有相同的倍数,这些倍数就是它们的公倍数,其中除0以外最小的一个公倍数,  叫做这几
 个数的最小公倍数。
  最小公倍数特点:倍数的只有最小的没有最大,因为两个数的倍数可以无穷大。


最大公因数和最小公倍数之间的性质:两个自然数的乘积等于这两个自然数的最大公约数和最小公倍数的乘积。最小公倍数的计算要把三个数的公有质因数和独有质因数都要找全,最后除到两两互质为止。

求解最小公倍数的方法有 —直接暴力求解,另一种是—根据最大公约数和最小公倍数的关系来求解。


 暴力求解


两个数的最小公倍数肯定是两个数中值比较大的那一个,然后从较大值max一直递增,每递增一次,就拿max与n,和m进行取模,一旦max%n= =0和max%m= =0都成立那这个max就是最小公倍数啦。

第一种方法:思想就是找到既能整除a又能整除b的数m,这个数肯定是大于或等于a,b两个数的;那就先找出a,b中的最大值,然后给最大值每次自增循环取模a,b看能不能得0.先利用条件操作符算出最大值m。
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main()
{
  int n, m;
  scanf("%d%d", &n, &m);
  int max = (n > m ? n : m);//把最大值赋给max;
  while (max % n != 0 || max % m != 0)//max%n!=0或者max%m!=0时c肯定不是公倍数;继续找
  {
    max++;//只有当max%n==0和max%m==0同时满足才能跳出循环;
  }
  //跳出循环的max就是最小公倍数,因为max+1每次往上加一;
  printf("%d", max);
  return 0;
}


第二种方法,比第一种效率要高,利用m/a=整数原理(如果m是最小公倍数)。 最小公倍数一定是较大者的整数倍m/a = i(m是最小公倍数,那么i肯定也是整数中最小的)。那么 i*a%b==0这时就是最小公倍数。

int main()
{
  int a, b;
  scanf("%d%d", &a, &b);
  int i = 1;//i从1开始不能从0开始
  while ((i * a) % b != 0)
  {
    i++;//i*a 如果能取模b==0那么i*a肯定是a,b,的公倍数,因为i从小到达递增,
    //所以一开始的i就是最小公倍数;
  }
  printf("%d", i * a);
  return 0;
}


  根据关系求解:     最小公倍数=一个数/最大公约数


最小公约数可以根据辗转相除法来求解。

代码如下:


int main()
{
  int a, b, c;
  scanf("%d%d", &a, &b);
  int a1 = a;
  int b1 = b;
  while (c = a % b)//根据辗转相除法求最大公约数。
  {  
    c = a % b;
    a = b;
    b = c;
  }
  //最后b是最大公约数。注意!这里a b 的值已经变化,不能再使用了,所以
  //上面需要重新赋值给新的变量。
  printf("%d", a1*b1 / b);
  return 0;
}


当然还有许多方法可以求最大公约数啦也可以暴力求解。

以上只是萌新的想法,希望大家可以相互指教喔66a3aa7ce3da4e7faba7bbb285679762.png

相关文章
|
14天前
|
算法
求最大公约数和最小公倍数的算法
求最大公约数和最小公倍数的算法
27 0
|
1天前
|
移动开发 算法
最大公约数和最小公倍数
最大公约数和最小公倍数。
7 2
|
14天前
|
算法
详解最大公约数和最小公倍数
详解最大公约数和最小公倍数
|
14天前
|
算法 Python
最大公约数算法
最大公约数算法
|
14天前
|
算法 Python
最小公倍数算法
最小公倍数算法
|
11月前
|
人工智能 BI
求最大公约数和最小公倍数
求最大公约数和最小公倍数
55 0
|
算法
求最大公约数和最小公倍数的几种算法
求最大公约数和最小公倍数的几种算法
90 0
求解最大公约数和最小公倍数
求解最大公约数和最小公倍数
求解最大公约数和最小公倍数
求最大公约数最小公倍数
求最大公约数最小公倍数
99 0

热门文章

最新文章