C语言程序:用“辗转相除法”求两个正整数的最大公约数(程序填空)

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

#include <stdlib.h>

int main()

{

int a, b,r

scanf("%d %d", &a, &b)

while (b != 0)//当其中一个数为0，另一个数就是两数的最大公约数

{

r = a%b

a = b

b = r

}

printf("最大公约数%d\n", a)

system("pause")

}

例子：

105252

252％105＝42；

105％42＝21；

42％21＝0；

即21为105与252的最大公约数

扩展资料：

while语句若一直满足条件，则会不断的重复下去。但有时，需要停止循环，则可以用下面的三种方式：

一、在while语句中设定条件语句，条件不满足，则循环自动停止。

如：只输出3的倍数的循环；可以设置范围为：0到20。

二、在循环结构中加入流程控制语句，可以使用户退出循环。

1、break流程控制：强制中断该运行区内的语句，跳出该运行区，继续运行区域外的语句。

2、continue流程控制：也是中断循环内的运行 *** 作，并且从头开始运行。

用辗转相除法（即欧几里得算法）求两个正整数的最大公约数.

解析：

设两个数m,n,假设m>=n,用m除以n,求得余数q.若q为0,则m为最大公约数；若q不等于0,则进行如下迭代：

m=n,n=q,即原除数变为新的被除数,原余数变为新的除数重复算法,直到余数为0为止.余数为0时的除数n,即为原始m、n的最大公约数.

迭代初值：m,n的原始值；

q=m%n

m=n

n=q

迭代条件：q!=0

例如：m=8n=6

q=m%n(8%6==2)

m=n(m==6)

n=q(n==2)

因为：(q==2)!=0,重复算法：

q=m%n(6%2==0)

m=n(m==2)余数为0时的除数n为最大公约数,n值赋给了m,所以输出m的值

n=q(n==0)

因为：q==0 所以最大公约数为m的值

源程序：

#include

void main()

{

int m,n,q,a,b

printf("Enter two integers:")

scanf("%d%d",&a,&b)

m=a

n=b

if(n>m)

{

int z

z=mm=nn=z//执行算法前保证m的值比n的值大

}

do

{

q=m%n

m=n

n=q

}while(q!=0)

printf("The greatest common divisor of")

printf("%d,%d is %d\n",a,b,m)

}

希望对你有所帮助!

---