C语言程序问题求两个整数最大公约数和最小公倍数求分析思路.

来源：学生作业帮助网编辑：六六作业网时间：2024/12/23 03:06:33

C语言程序问题求两个整数最大公约数和最小公倍数求分析思路.C语言程序问题求两个整数最大公约数和最小公倍数求分析思路.C语言程序问题求两个整数最大公约数和最小公倍数求分析思路.辗转相除法最大的用途就是用

C语言程序问题求两个整数最大公约数和最小公倍数求分析思路.
C语言程序问题求两个整数最大公约数和最小公倍数求分析思路.

C语言程序问题求两个整数最大公约数和最小公倍数求分析思路.
辗转相除法最大的用途就是用来求两个数的最大公约数.
用（a,b）来表示a和b的最大公约数.
有定理：已知a,b,c为正整数,若a除以b余c,则(a,b)=(b,c).
例：求 15750 与27216的最大公约数.

∵27216=15750×1+11466 ∴（15750,27216）=（15750,11466）
∵15750=11466×1+4284 ∴（15750,11466）=(11466,4284)
∵11466=4284×2+2898 ∴(11466,4284)=（4284,2898）
∵4284=2898×1+1386 ∴（4284,2898）=（2898,1386）
∵2898=1386×2+126 ∴（2898,1386）=（1386,126）
∵1386=126×11 ∴（1386,126）=126
所以（15750,27216）=216
辗转相除法比较适合用来求两个比较大的数的最大公约数.

C语言程序问题 求两个整数最大公约数和最小公倍数 求分析思路.

C语言程序问题求两个整数最大公约数和最小公倍数求分析思路.