【C语言】实现辗转相除法求最大公约数

目录一、算法简介二、 C语言代码一、算法简介辗转相除法又称欧几里得算法是指用于计算两个正整数ab的最大公约数。。应用领域有数学和计算机两个方面。计算公式gcd(a,b) gcd(b,a mod b)。两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。以除数和余数反复做除法运算当余数为 0 时取当前算式的除数为最大公约数。例求24和18的最大公约数1、24 / 18 1 ...... 62、18 / 6 3 ....... 0当余数为0时当前算式的除数即为最大公约数所以18和24的最大公约数为6二、 C语言代码//辗转相除法求余数 #includestdio.h int main() { int a; int b; scanf(%d %d, a, b); int c a % b; while (c) { a b; b c; c a % b; } printf(%d, b); return 0; }运行结果从运行结果可以看出此方法与a和b的大小顺序无关