三种方法求最大公约数(C语言版)

首先给大家推荐一下我老师大神的人工智能教学网站。教学不仅零基础,通俗易懂,而且非常风趣幽默,还时不时有内涵黄段子!点这里可以跳转到网站

问题描述:用三种方法求两个的整数的最大公约数。

算法分析:

1.相减法:输入两整数a和b,(1)如果a>b,a=a-b;(2)如果a<b,b=b-a;(3)如果a=b,a或b就为这两个整数的最大公约数

 (4)如果a!=b,则再执行(1)或(2)

程序实现如下图:

2.穷举法:输入两个整数a和b,(1)定义c;(2)如果a>b,则c=b;(3)如果a<b,则c=a;

     (4)如果a%c||b%c!=0,则执行c–;(5)如果a%c&&b%c==0,则c为最大公约数。

程序实现如下图:

3.辗转相除法:输入两个整数a和b,(1)如果a%b=c,c为0,则b为两数的最大公约数;

     (2)如果c!=0,则令a=b,b=c,执行(1);

程序实现如下图:

并且如上图所示,可以利用两数之积/两数的最大公约数=其最小公倍数的关系,顺带求出两数的最小公倍数。

另外,附上程序主函数的代码,如下图:

以上就为用三种方法求两个整数最大公约数的全过程。

点这里可以跳转到人工智能网站