求两个数的最大公约数和最小公倍数

时间:2023-01-01 19:02:03

        对于求解两个数的最小公约数,能够通过两种方法进行解决,下面是具体的程序:

程序一:

  • #include <stdio.h>

  • int main()

  • {

  •          int a[2];

  •          int i,min,max;

  •          for(i=0;i<2;i++)

  •                scanf("%d",&a[i]);

  •          if(a[0]<a[1])

  •           {

  •                 min=a[0];

  •                 max=a[1];

  •            }

  •           else

  •            {

  •                 min=a[1];

  •                 max=a[0];

  •            }

  •           for(i=min;i>0;i--)

  •                 if(max%i==0&&min%i==0)

  •                  { 

  •                           printf("%d ",i);

  •                             break;

  •                   }

  • return 0;

  • }

 

程序二:

  • #include <stdio.h>

  • int main()

  • {

  •         int num1=0;

  •         int num2=0;

  •         int tmp;

  •                scanf("%d%d",&num1,&num2);

  •         while(tmp=num1%num2)

  •         {

  •                 num1=num2;

  •                 num2=tmp;

  •         }

  •          printf("最大公约数:%d\n",num2);

  • return 0;

  • }

 

        对于上面的两个程序,第一个程序利用最大公约数最大是两个数中较小的特点,通过循环实现让较小的整数逐渐较小,判断最大数师傅能够整除依次减小后的整数,如果能够整除,则这个数为这两个整数的最大公约数。

        第二个程序的算法核心是辗转相除法,定义两个整数,通过辗转相除的方式直接能够得到两个整数的最大公约数。相比较来说,第二个方法能够更加简单。

       

         对于求解两个整数的最小公倍数,可以在求解最大公约数的基础上,通过两个整数之积除以最大公约数求得最小公倍数。下面是具体程序:

  • #include <stdio.h>

  • int main()

  • {

  •        int num1=0;

  •        int num2=0;

  •        int tmp,a,b;

  •              scanf("%d%d",&num1,&num2);

  •              b=num2;

  •        while(tmp=num1%num2)

  •        {

  •               num1=num2;

  •               num2=tmp;

  •         }

  •               a=(num1*b)/num2;

  •         printf("最大公约数:%d\n",num2);

  •         printf("最小公倍数:%d\n",a);

  • return 0;

  • }

 

本文出自 “无心的执着” 博客,请务必保留此出处http://10740590.blog.51cto.com/10730590/1699681