C_最大公约数和最小公倍数

━╅  C  ╆━ | 2007-10-08 06:51:00 | 阅读 5588 次 | 评论(0)

求任意两个正整数的最大公约数和(GCD)和最小公倍数(LCM)

*问题分析与算法设计
手工方式求两个正整数的蝚大公约数的方法是用辗转相除法,在程序中可以模拟这种方式。

*程序说明与注释
#include<stdio.h>
int main()
{
int a,b,num1,num2,temp;
printf("Input a & b:");
scanf("%d%d",&num1,&num2);
if(num1>num2) /*找出两个数中的较大值*/
{
temp=num1; num1=num2; num2=temp; /*交换两个整数*/
}
a=num1; b=num2;
while(b!=0) /*采用辗转相除法求最大公约数*/
{
temp=a%b;
a=b;
b=temp;
}
printf("The GCD of %d and %d is: %d\n",num1,num2,a); /*输出最大公约数*/
printf("The LCM of them is: %d\n",num1*num2/a); /*输出最小公倍数*/
}

*运行结果
1.Input a & b: 20 55
The GCD of 20 and 55 is: 5
The LCM of them is: 220

2.Input a & b: 17 71
The GCD of 17 and 71 is: 1
The LCM of them is: 1207

3.Input a & b: 24 88
The GCD of 24 and 88 is: 8
The LCM of them is: 264

4.Input a & b: 35 85
The GCD of 35 and 85 is: 5
The LCM of them is: 595

*思考题
求一个最小的正整数,这个正整数被任意n(2<=n<=10)除都是除不尽的,而且余数总是(n-1)。例如:被9除时的余数为8。要求设计一个算法,不允许枚举与除2、除3、....、除9、除10有关的命令,求出这个正整数。

文章评论,共0条
游客请输入验证码
浏览365594次