目录
- 穷举法
- 辗转相除法
- 辗转相减法
穷举法
(1) i= a ,b中较小的数
(2)若a,b能同时被i整除,则i即为最大公约数,结束
(3)若不能,则 i–,再回去执行(2)
#include<stdio.h> int main() { int i = 0; int j = 0; scanf("%d %d", &i, &j); int k = i > j ? i : j;//i>j,k=i;i<j,k=j while(1) { if (i%k == 0 && j%k == 0) { printf("最大公约数为;%dn", k); break; } k--; } return 0; }
辗转相除法
辗转相除法求两个数的最大公约数的步骤如下:
(1)先用小的一个数除大的一个数,得第一个余数;
(2)再用第一个余数除小的一个数,得第二个余数;
(3)又用第二个余数除第一个余数,得第三个余数;
这样逐次用后一个数去除前一个余数,直到余数是0为止。那么,最后一个除数就是所求的最大公约数。
#include<stdio.h> int main() { int a = 0; int b = 0; int c = 0; scanf("%d %d", &a, &b); while (c = a%b) { a = b; b = c; } printf("%dn", b); return 0; }
辗转相减法
两整数a和b:
(1) 若a>b,则a=a-b
(2)若a<b,则b=b-a
(3) 若a=b,则a(或b)即为两数的最大公约数,结束
(4)若a≠b,则再回去执行(1)
#include<stdio.h> int main() { int a = 0; int b = 0; scanf("%d%d", &a, &b); int ret = 0; while (1) { if (a < b) { int tmp = 0; tmp = a; a = b; b = tmp; } ret = a - b; if (ret == b)//判断 { printf("ret = %d", ret); break; } else//交换 { a = b; b = ret; } } return 0; }
以上就是c语言最大公约数示例详解的详细内容,更多关于c语言最大公约数的资料请关注<计算机技术网(www.ctvol.com)!!>其它相关文章!
需要了解更多c/c++开发分享C语言最大公约数示例教程,都可以关注C/C++技术分享栏目—计算机技术网(www.ctvol.com)!
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/965359.html