您当前的位置： 首页 > 慢生活 > 程序人生 网站首页程序人生

c语言实现輾轉相除法求最大公約數

发布时间：2021-04-29 22:00:23编辑：雪饮阅读（）

 辗转相除法是什么鬼？


辗转相除法又称欧几里得算法，
欧几里得算法是用来求两个正整数最大公约数的算法。古希腊数学家欧几里得在其著作《The Elements》中最早描述了这种算法,所以被命名为欧几里得算法。
扩展欧几里得算法可用于RSA加密等领域。
假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法，是这样进行的：
1997 / 615 = 3 (余 152)
615 / 152 = 4(余7)
152 / 7 = 21(余5)
7 / 5 = 1 (余2)
5 / 2 = 2 (余1)
2 / 1 = 2 (余0)
至此，最大公约数为1
以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1。
那么利用该原理我们就可以实现c语言中以辗转相除法解开最大公约数了。
#include <stdio.h>
int hcf(int n1, int n2);
int main()
{
   int n1, n2;
   printf("输入两个正整数: ");
   scanf("%d %d", &n1, &n2);
 
   printf("\n %d 和 %d 的最大公约数为 %d", n1, n2, hcf(n1,n2));
   return 0;
}
 
int hcf(int n1, int n2)
{
    if (n2 != 0){
              printf("\n n1=>%d與n2=>%d取余為:%d \n",n1,n2,n1%n2);
              /*
              每次右操作數作爲下一次的左操作數，下次的右操作數為上次左右操作數的餘數
              這樣正符合了辗转相除法，這裏不必擔心左操作數大于右操作數的情況
              例如本次是n2=2,n1=1,則下次n1%n2=1%2=1則
              下次為n1=2(上次傳遞的n2),n2=1(上次的取余)，則下次n1%n2=2%1=0
              那麽接下來n2=0（上次的取餘），n1=1(上次傳遞的n2)，則沒有下次了，因爲判斷n2不能等於0
              那麽接下來範圍n1，既是1，這個1就是1和的最大公約數。
              */
              return hcf(n2, n1%n2);
       }
    else {
              return n1;
       } 
}