如何求两个正整数最大公约数和最小公倍数。

时间:2023-01-01 19:01:33
  面试题目:输入两个正整数 m n ,求其最大公约数和最小公倍数。    
在循环中,只要除数不等于 0 用较大数除以较小的数将小的一个数作为下一轮循环的大数取得的余数作为下一轮循环的较小的数,如此循环直到较小的数的值为 0 ,返回较大的数,此数即为最大公约数,最小公倍数为两数之积除以最大公约数
 
 分析: 首先这个题目读懂题意很重要,把这句话:"用较大数除以较小的数将小的一个数作为下一轮循环的大数取得的余数作为下一轮循环的较小的数"读懂这句这题就没有什么难度了,这句话翻译过来就是:
第一步:将较大的数 x,除以较小的数y ,并取余 k =x%y;
第二步:将第一步较小的数y作为这一轮的较大数,第一轮的余数 k做为这一轮的较小的数,然后以此循环.
   代码如下:为方便初学者阅读,代码比较简单易懂.
       @Test
      public void fun01() {
          Scanner sc = new Scanner(System. in );
          System. out .println( "请输入一个正整数" );
           int a = sc .nextInt();
          System. out .println( "请再输入一个正整数" );
           int b = sc .nextInt();
           //求最大公约数
           int n = fun( a , b );
           //最小共倍数数初始化
           int m =( a * b )/ n ;
          System. out .println( "最大公约数:n =" + n );
          System. out .println( "最小共倍数数初始化m =" + m );
     }
      public int fun( int x , int y ){
           int t ;
           //总是使x最大
           if ( x < y ){
               t = x ;
               x = y ;
               y = t ;
          }
           //y不为0就一直循环
           while ( y !=0){
               if ( x == y ){
                    return x ;
              }
               int k = x % y ;
               //小的数作为下一轮的大数
               x = y ;
               //余数作为下一轮较小的数
               y = k ;
          }
           return x ;
     }