Midterm Question 3

Question

Write a program that asks the user to enter two integers, then calculates and displays their greatest common divisor (GCD) and their Least common multiple (LCM).

寫一個輸入兩個整數 輸出它們的最大公因數程式

Hint: Use Euclidean Algorithm

使用歐幾里得演算法

LCM:

In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers a and b, usually denoted by LCM(a, b), is the smallest positive integer that is divisible by both a and b.

What is the LCM of 4 and 6?

Multiples of 4 are:

4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, ...

and the multiples of 6 are:

6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, ...

Common multiples of 4 and 6 are simply the numbers that are in both lists:

12, 24, 36, 48, 60, 72, ....

So, from this list of the first few common multiples of the numbers 4 and 6, their least common multiple is 12.

 

Example input: 

12 28

Example output (first number is GCD, second number is LCM):

4 84

 

Answer 1

Hidden content!
#include  * ** ** * *  **
//gcd and lcm
int main(void)
{
* *       *  ***   * ***** * n,m,i,gcd, j,k,lcm;
*  *    * *  ****   ** *     *** *       ** * **** &n, &m);
   * **** * ***   *  **  ***     i<=n  *****  ***  i<=m; i++)
* * ** **   **          * * 
****   ** ***      *  * * ******   ** * * ****   * *      *   *  *   *     *  m%i==0)
*   * * *** **    * * * *  ***  *   * *  * ***    *** ** ** *   * * **  *   ** **** *  * 
   ** ** *  * * *** *  * *
* ***   *        ** ** ** *  *   *  *   * * ", gcd);

******* **  * * *    *** *   * k>=n && k>=m; k--)
*****  **  *** ** * **  **   * **
   * * **   * **** * **  *  *      *  ****   k%m==0)
   *** *  ***   ** *  *** *  ***
*** **** *  ***  ** **

***** ** *** *  ***       *****         * ** **  **** **


  * * *****     ** *  ***   ***** *   0;

}

Comments

Case 0: Correct output
Case 1: Correct output
Case 2: Correct output
Case 3: Correct output
Case 4: Correct output

Answer 2

Hidden content!
#include<stdio.h>

int main() {
 ***  ***  ****** **  *  * a,b,tmp,x,y;
*   **   *       * * *   ** * ***   * %d", &x ,&y);
 *** * ***   *  * * **       * *
 **     ** ** ** * * *** * **   ***
* **      **    ** * *   **  *      ** {
  *      **** ***   **** *   * ** **    **  *  * * * 
*  * **** ****** *  **    ** *  *    ***   * *  * * *     *** *
** **** * **  *  * *     ** * *      * * * **   *     
 *  * * ****  * ** ***** 
 *  **    * ** ** ** * * *  ** *  * *  **   %d", b, b*(x/b)*(y/b));
}

Comments

Case 0: Correct output
Case 1: Correct output
Case 2: Correct output
Case 3: Correct output
Case 4: Correct output

Answer 3

Hidden content!
#include<stdio.h>
int main(){
 * * * ** *  *  *     * ***  a,b;
** ** *** ****   *   * **     * *  gcd,lcm;
*  ** * * * ** *    **** **  ****    ***  %d",&a,&b);

*    *  *****    *****  ** *** ag=a,bg=b;
** * * ** ****   **    **** * *    *  *****
   * *** **    ** *       * ******* **   *  **
**** *****    * ** ***     *   **  * **  *  *     *  temp;
 ***  ** * *    ** *      *** ****** *** *     ** **  **  bg=ag, ag=temp;
** ** *  **    **  **** *  * 

** *   *  ** *     ***** ***** i=1,al=a,bl=b;
 **   ** *   * ** **  **  ****   *  al%bl!=0 ) {
** *  **   *   **   *******   *** ***** ******  *  *      *
***   ** *    **  * * ****  ****   *  * ******  *   ** **  
  * * *** * * **        

  *  *  *  *  **   *  ***   ****  ** * *  **  * %d",bg,al);
   ** *  *  ****** *******   * **  * 0;
}

Comments

Case 0: Correct output
Case 1: Correct output
Case 2: Correct output
Case 3: Correct output
Case 4: Correct output

Answer 4

Hidden content!
#include<stdio.h>
int a,b,i,q=1;
int main()
{
scanf("%d",&a);
scanf("%d",&b);

for(i=a;i>=1;i--)
{
    if(a%i==0)
   * *  * * *** ***    ** *  *   * *   **     * **    *  
 **  **** * ****** ** ** * *   *  *     *   **    ***  **  * *   *** *  *** *****  *  *   * * * 
*** ***  *  *  *    * *  ****** * ****  * *  *** *  * *  ** *** * *** *   ******* **  * *  **** **   * * ** *  ** *  * *** **    *** **  ** **  *    * **  * 
**   **  * * *   ***   *    ** * *   **  *  ****   *  * **** *********  ** ***** *  * **  ***      *****    * * *       * *   ****  *     **
  ** ***   **     ** ** *  **    ** **  * **                  *****  * ****      ** * ** *    * *     * *** * * ** ***** **  ** **    * ***    * *   **  ** **  ***  * *    *** * *
    * **** *    **   ******** ***    *   * ** ****   *  * *  ** ** *    * **  *  ** *** ** * **       ** *   ******    *** *** * ** * ** **  *      ** * *  ***  **  ",i);
  * *  ** ** *    **** * *   * *    * *    **   *  ***  *****     *  ***  * ********    ** *  * *     *  * **    ** **      * * * ** **    ** * ***** * *    *
***   *  *   ***  ******     ***    **** **  *  * *   *    ** **   *   * **  *    *   *  **** * *  * * *****    * **  *   *  * **  ******  
  *** *********** ***  **  ** ***  **** **** * ***
}


for(i=b;;i++)
{
    if(i%b==0&&i%a==0)
* ******* **     ***   *** *** *   *** *    ***   ** * 
* **  **** *** *****   ** *****   ** ** ** ** * * * *  ***   **  * *  ***** 
*    *  *  * *    ** * **  * *        *   ** ** ** ** ** *   
        }

}




}

Comments

Case 0: Correct output
Case 1: Correct output
Case 2: Correct output
Case 3: Correct output
Case 4: Correct output

Answer 5

Hidden content!
#include <stdio.h>\

int main()

{
    int a,b,i,j,k,flagGCD1,flagGCD2,flagLCM1,flagLCM2;
 * *  *** * ** *  * *  **** ****     *  %d",&a,&b);

    //GCD
    for (i=a;i>0;i--)
    {
*    ***  *  * *   * **   **    *  *   ***  *  **   **       * *    *
       *** **  *  **     *  **  * * * * * *****  *   * **   * **** (flagGCD1==0)
**********     *   *  * **   * * **  *   *  * **** 
    *   * ***  *  ***** * ***    *   *** **   * * * **** *  **   ** *  * * ****  ***  *    
*** *   * *   *   **** ** **   *  *   *   * *       ** *****   ***   * ** ** ***   ***  * (flagGCD2==0)
*** *  * *** *  *  * **  * *  ****  **      *   *  ** ***     ** *  **  * **** *  *  *
****      ** **   ***** ***  **    ** *   * * ** * ** *  * **  *   *   * * * ****   * * ***** ** *  * **  ****   *  *    ",i);
    ** * ***  **** ***     **  **** * * **   ** ***    ** *  * ** *    *   *  *********  * *        *
 ** * *  **  ** * ***     ** ** * * **   *****  * ** * *    * *******  *  *   **
  **** *  ******    *  **  ****** ***    * * * *
    }

    //LCM
    for (j=1;j;j++)
    {
******** * ** ****    *  ***** **  **  * * * ****     * *   ** ****
*******     * *  **  * *  * *****  ****  *  * **   *** * (k=1;k;k++)
*** **  * ***      *   *  ** *   ** ** *  * * *  ******* **  
** *  ***  * * ***  *     ** ******     ** *   ** * * *****  **  *  ** * *  ***** * ***
*  * *** *  **  **   **** **  *   ***    **** *    * **     *      ** ****** *    (flagLCM2==flagLCM1)
** **   ***  ****  ***   *   *  *** ***  * ******** **** ** *   ** ****  
*   *  * **     **   **  *** *   *  ** **   *    * *  ***     * *     *  ******   * ** ***  *  ** **    * *  **  * **    ** *    
 ***         * *  **   **** ***   *** * ***** ** * ***  ***  *  **  **    *  *** **    *  ***  ** *** *     *****
*  ** *  *   * * * *   ***** ***** ** *  * **  * ***   ** ***    *  *** *   *    ****
 ** * ****     *   * **** * **  ** * *** ****** *    *  *  *  ****     ***  *   *  *   (flagLCM2>flagLCM1)
*   * ***    *  * * *** *******  ***  ***   * * * * ** * **      *  **  * *  *  **   *
** * *        *** ** ****** * *   ** **      *  * * * *  *   * * * ** ** ** ** * * *   *   ***** * ***  *  
 * *  ** **  *    **        ** *  * ** **** **  **** ** *    * ****** * ***  ** 
** *** **  *       ***   **** **  ** * ***  ** 
**** * *  *****  *    **** * **   * ****  * ** ****  *   (flagLCM2==flagLCM1)
*   * *   * *****    ****  **      *  * * ***  
* * *   *   *  ** * **  ***   * **  *** * **** * ** *    ** * *  *  *  ** * ** *   **  *  
 *   *  **      *  ***    **   * * **   *  ******** * *** **   **  
    }

    return 0;

}

Comments

Case 0: Correct output
Case 1: Correct output
Case 2: Correct output
Case 3: Correct output
Case 4: Correct output

Answer 6

Hidden content!
#include<stdio.h>
int a,b,i,q=1;
int main()
{
scanf("%d",&a);
scanf("%d",&b);

for(i=a;i>=1;i--)
{
    if(a%i==0)
** ***** *   *   *** * *    *** **  ******** *******  *  *
 * *****     ** * * **  ** *       *** ****  ** * * **  *** *    *  ***** **** *  *  **  ** **  *  *
* *** **  * ***   * ***  * *********   * ***** *  **    ** *    *  * *  *  ***** ******** ***  * * ** ***    *** **** ** *  ***  * * **     * 
****   **   ** ** *  *  *****  *** *  * **  **  * **  ** * **  *  * *       **  **  *** ****  *  ***  *  **    ** ***     * *   **** **   *  ** *  * **** **
    * * *  * ** ** *   **      ***  *  * **   **** *  * * * ***  ** *    ****** * ****     *** * **     * *    **   ****   ** *   ** * ** *** **    * *** *      **   *   **    *
** **    * **   *  *   **   * * *** **     ** ** *  *      *    ** *     ***  ** * *  *  **  **  * **  **  ** **   ****  *  ******  *  ****  * **  ***   ** *    
***** * ** *  *  ***    * ** ***  *   * *  *  ** ***  *** **** * * * **    * **   *  **  **   **  **  * **  *** *******  * *  * *  *  ** *
* ** **    **  *** *   *     **    *** ** **** *  *  ***    *  **   * *  ** * *** * ***    *  * * **   ** *********  ***** * **     **** * *   ***
* *** ** ***  *   *  **  ** * * **  ** *    * ** ** **   ***
}


for(i=b;;i++)
{
    if(i%b==0&&i%a==0)
 **    *  ****    **  * **     * * * *** * ** *   
 ** *   *  *  * *     ***   *******        * *    * *  * *     *  *   **
  *    * ** **  *******   * *  ****    ** *    ****   *  *
        }

}




}

Comments

Case 0: Wrong output
Case 1: Wrong output
Case 2: Wrong output
Case 3: Wrong output
Case 4: Wrong output

Answer 7

Hidden content!
#include <stdio.h>
#include <stdlib.h>

int main()
{
**      ** *    **   ** **   a,b,smaller,i;

** * ***   *  *  ****  *  *****   *****     *  *** *  *  ***  * * * 

 **   ** *   * * ****     ** **   * ** **
* **    * *** *     * *  ** *      *  * *  *   ** * **** *** 
 **  *    *    * **  * *      
** *  **   * **    ****        ** *    * *   * * * ** *

**   **  ***  * **** ** *  ******* *   *  * *   **   *
***    * * *  ***    ** * ***    **  **  *** ***   *    * && b%i==0)
  ** **  * * **    **  * *  *     **** * * * *   *    * **** ** **    * **  *  *

  * ***    *    ***  * *******   * * ** *         *** *****  *   *  *   **    %d",i,(a/i)*b);

 ***  *****    ***  *   *     * 0;

}

Comments

Case 0: Wrong output
Case 1: Wrong output
Case 2: Wrong output
Case 3: Wrong output
Case 4: Wrong output

---

Case 0: Wrong output
Case 1: Wrong output
Case 2: Wrong output
Case 3: Wrong output
Case 4: Wrong output

---

Case 0: Correct output
Case 1: Correct output
Case 2: Correct output
Case 3: Correct output
Case 4: Correct output

Answer 8

Hidden content!
#include<stdio.h>
int main()
{
**  *   * ** * ***        i,n1,n2,a,gcd,lcd;
***  * ** * *    **        * **
   *   *   ** **  ** *  ** ** **   ***** *  %d",&n1,&n2);
** **   ** *  **** **  *     * **  **** **     || i<=n2; i++)
      ***   * ** * ** *  * *****
 **   * ***       * ***     ** * *  * *    *  *** *   **  *    && n2%i==0)
**  *** * ****    ****      *  * *       * ***     
*** ** * ** * * * * ******* **** ***  **      **  **  *   *  *** ******* **  *   *  * *
*   ** * *  ** * ** *  ** ** *** **     *    ***  
   ** * **  *  *  *  * *     *  
  ***** * ***** * *           * ** **    * * **  && a>=n2;a--)
    {
 *   * *    * * ******    ****** * *  * ******      *    ** && a%n2==0)
 ** *  **** * **  *   ** *   ** * *** *   *****  *    
 ** ** ** * * **   ** *** ** *** *  * * ***  *******   * ****   **   **  * *   ** 
* ** * *** ****  *** *   ***   *** **  **     * *  ****
    ** *     ***   *   *    *  
*  * *  * ***        *  **** ***   * * * ***  %d",gcd,lcd);
  * * **  *  * ***    ** * **  0;
}

Comments

Case 0: Correct output
Case 1: Correct output
Case 2: Correct output
Case 3: Correct output
Case 4: Correct output

Answer 9

Hidden content!
#include   ****  ** *
int main (){
int i,j,k;
  * *     **  * * *  * *  * 
   *     * ** **   *   *  **   ****  *  
 * * **    **** *
*  ** ** ***** ** ***  ***** *  *      * * ** * * *
**** ******  *  ******  ** * *  ***
*** * ***  * **   ** 


return 0;
}

Comments

prog.c: In function 'main':
prog.c:6:10: error: expected expression before '=' token
 while(i!==0)||(j!==0){
          ^

Answer 10

Hidden content!
#include <stdio.h>
#include <stdlib.h>

int a,b,GDC,LCM;

int Get_GDC(int a1,int a2){

*   ** **   * *  ***** ***  ** i;
  * ****  **   ***  **** result=1;
  ** *** ****  **  * * ******  **   *   ** 
 * *  *  *     **   ** *  * ** ****  *   * **    *  *** * ** *  && a2%i==0){
   * * *****   *****         *****  *** ** *   *  *******   **  **   * ***      **   = i;
*   *** *****   *       ***    ** *  ***  *** * * *    ** 
  ** ** ** * **  ****    ***  

****  * ****    *   * * *** ** result;
}
int Get_LCM(int a1,int a2){

 *  ** *     ** * ** *  * * i;
* *     * *  ** ***  * ** * *  result=1;
* * **** * **  *  *  * ** **   * ** *** *     ***** 
***  * * *        ****      * * **  **  *   **    * *   *       && i%a2==0){
**    **  *     * *  ** ***   * **   ***  * **  *** **   ***  **  *** *   *  ** ** * * * = i;
** *  *** *   *        *** *  * *** ****  **   **   
    * **** *      **    * **

    ** *   **    *****  *   result;
}


int main(){

   *    **     ** *  **  *  *      *  ** ** ****  *  * * 

** ** * *  ** **    *   *   *     **  *   
 ******      ******     * *  * *  **** ** 



**   *  **   *  * *   *******  ** * *  * *      %d", GDC, LCM);
*  ******  *    **   * * ****     0;
}

Comments

Case 0: Correct output
Case 1: Correct output
Case 2: Correct output
Case 3: Correct output
Case 4: Correct output