辗转相除法初识-526互联

第一种.求两数的最大公约数,使用的是欧几里德算法。

#include <stdio.h>
int hcf(int n1, int n2);
int main()
{
   int n1, n2;
   printf("输入两个正整数: ");
   scanf("%d %d", &n1, &n2);
 
   printf("%d 和 %d 的最大公约数为 %d", n1, n2, hcf(n1,n2));
   return 0;
}
 
int hcf(int n1, int n2)
{
if (n2 != 0)
   return hcf(n2, n1%n2);//欧几里得，辗转相除法 
   
else 
   return n1;

第二种.

#include <stdio.h>
int main()
{
int n1, n2;

printf("输入两个数，以空格分隔: ");
scanf("%d %d",&n1,&n2);
 
while(n1!=n2)
{
if(n1 > n2)
n1 -= n2;//如果输入的两个数为 18 和 12，那么执行过程如下：
//第一轮循环：n1 = 18, n2 = 12，n1 大于 n2，所以执行 n1 -= n2，得到 n1 = 18 - 12 = 6。
//第二轮循环：n1 = 6, n2 = 12，n1 小于 n2，所以执行 n2 -= n1，得到 n2 = 12 - 6 = 6。
//此时，n1 和 n2 的值相等并且都为 6，所以循环停止.它就是输入的两个数 18 和 12 的最大公约数。
else
n2 -= n1;
}
printf("GCD = %d",n1);
 
return 0;
}