[C++知识库]c语言 用辗转相除法求两个数的最大公约数

#include<stdio.h>

int main()
{
?? ?int a, b;
?? ?int r = 1;
?? ?printf("请输入两个数：");
?? ?scanf("%d %d", &a, &b);
?? ?while (r != 0)
?? ?{
?? ??? ?r = a % b;
?? ??? ?a = b;
?? ??? ?b = r;
?? ?}
?? ?printf("最小公倍数：%d", a);


?? ?return 0;

}

辗转相除法

用图形理解

用正方形去填充长方形

1.先放两个最大的正方形边长为28

78/28=2...16

再用边长为16的正方形去填充

28/16=1...12

再用变成为12的正方形去填充

16/12=1.....4

12再用边长为4的正方形去填充

12/4=3.....0

即可理解为

78/28=2...16

28/16=1...12

16/12=1....4

12/4=3.....0

整个边长为28和72长方形可由n多个边长为4的小小正方形组成

即78和18的最大公约数为4

?

?

?

?