这是我写的,不过是用辗除法的,我运行过,没有错,有错请指出,运行环境是VC++6.0
#include <stdio.h>
void main()
{
int a,b,c,d,t;
printf("请输入两个整数:");
scanf("%d%d",&c,&d);
a=c;
b=d;
while(b!=0)
{
t=a%b;
a=b;
b=t;
}
printf("最大公约数是:%d\n",a);
printf("最小公倍数是:%d\n",c*d/a);
}
我现在不想用辗除法,那可以怎么样编写呢?请高手指教,谢谢!
----------------解决方案--------------------------------------------------------
你要发现新算法啊
关注ing
----------------解决方案--------------------------------------------------------
#include <stdio.h> void main() { int a,b,i,j; printf("请输入两个整数:"); scanf("%d%d",&a,&b); i = 1; j = 1; while(1) { i++; if( (a % i) == 0 && (b % i == 0) ) j = i; else if (i > (a > b ? a : b) ) break; }
printf("最大公约数是:%d\n",j); printf("最小公倍数是:%d\n",a*b/j); } PS: 没有经过严格测试,楼主看看能不能满足你的要求
----------------解决方案--------------------------------------------------------
楼上的没错
----------------解决方案--------------------------------------------------------
三楼的算法效率不高,建议使用顶楼的算法,欧几里德的辗转相除法。
----------------解决方案--------------------------------------------------------
#include <stdio.h> #include <conio.h>
int gcd(int,int);
int main() { int m,n; printf("Please input two numbers: "); scanf("%d %d",&m,&n); printf("The greatest common divisor is %d\n",gcd(m,n)); printf("The lowest common multiple is %d\n",m*n/gcd(m,n)); getch(); return 1; }
int gcd(int m,int n) { int r; do { r=m%n; m=n; if(r) n=r; } while(r); return n; }
----------------解决方案--------------------------------------------------------
人家不是都说了不能用Euclid算法的嘛?
----------------解决方案--------------------------------------------------------
三楼的没错,谢谢指教,如果能写出你是怎么样想的,那就更加完美了
----------------解决方案--------------------------------------------------------
很简单了
首先找出他们的公约数
在找出公约数中最大的
因为只有整数才有公约数的说法
所以我们可以从1开始迭代
迭代不长为1
----------------解决方案--------------------------------------------------------