回 帖 发 新 帖 刷新版面

主题:[讨论]关于最大公约数和最小公倍数的问题

main()
{int m,n,a,b,temp,answer1,answer2;
 printf("please input two integer numbers:\n");
 scanf("%d%d",&m,&n);
 if(m<n)
    {temp=m;m=n;n=temp;}
 a=m;b=n;
 while(b!=0)
  {temp=a%b;
   a=b;
   b=temp;
  }
 answer1=a;
 answer2=m*n/a;
 printf("the greatest common divisor is %d\n",answer1);
 printf("the lease common multiple is %d\n",answer2);
}


_________________________________________________________________________

main()
{int m,n,temp,answer1,answer2;
 printf("please input two integer numbers:\n");
 scanf("%d%d",&m,&n);
 for(answer1=m;;answer1--)
   if(m%answer1==0&&n%answer1==0) break;
 for(answer2=m;;answer2++)
   if(answer2%m==0&&answer2%n==0) break;
 printf("the greatest common divisor is %d\n",answer1);
 printf("the lease common multiple is %d\n",answer2);
}



这是两种写法,我想请问,这样写的算术方法是什么,谢谢了

回复列表 (共2个回复)

沙发

1. 辗转相除法

2.
第一个循环:如果m,n能除尽[m->1]之间的某个数,显然这个数就是最大公约数
第二个循环:m以上最小能同时除尽m,n的数就是二者的最小公倍数

板凳

楼主有兴趣可以翻翻D.E.Knuth的<< The Art of Computer Programming>>

我来回复

您尚未登录,请登录后再回复。点此登录或注册