欧几里德算法(求两个正整数的最大公约数)

时间:2022-09-08 09:46:20

/*欧几里德算法:辗转求余
  原理: gcd(a,b)=gcd(b,a mod b)
  当b为0时,两数的最大公约数即为a

  getchar()会接受前一个scanf的回车符
*/

#include<stdio.h>

void main()
{
    int temp;
    int a,b;
    scanf("%d",&a);
    scanf("%d",&b);
    printf("the greatest common factor of %d and %d is ",a,b);
    while(b!=0)
    {
        temp=b;
        b=a%b;
        a=temp;
    }
    printf("%d\n",a);
    getchar();
    getchar();
}