Find the greatest common divisor and the least common multiple (C language)

---

One 、 subject

Write two functions , Find the maximum common divisor and the minimum common multiple of two integers respectively , Call these two functions with the main function . Two integers are entered by the keyboard .

Two 、 Analysis and code

1. Ideas

• greatest common divisor ： The largest of the common divisors of two or more integers . Calculate by rolling division .
• Minimum common multiple ： Two or more integers share a multiple divided by 0 The smallest one outside . Because the product of two numbers is equal to the product of the greatest common divisor and the least common multiple of the two numbers , therefore , The least common multiple of two numbers is equal to the product of these two numbers divided by the greatest common divisor .
• Analysis methods ： Define two functions respectively , And two variables a,b. The first function uses the rolling division method to find a,b Maximum common divisor of , hypothesis a>b, Make a/b Get the remainder r, then b As divisor ,r As divisor , Get the remainder … Until the remainder is 0. The second function uses the above formula to obtain the least common multiple of two numbers .

2. Code

The code is as follows ：

#include <stdio.h>
#include <stdlib.h>

int main()
{
    
    int Greatest_Common_Divisor(int a,int b);       // Function declaration 
    int Least_Common_Multiple(int a,int b,int m);  // Function declaration 
    int a,b,m,x;
    scanf("%d,%d",&a,&b);
    m=Greatest_Common_Divisor(a,b);
    x=Least_Common_Multiple(a,b,m);
    printf("%d and %d The greatest common divisor of :%d\n",a,b,m);
    printf("%d and %d The minimum common multiple of is :%d\n",a,b,x);
    return 0;
}

int Greatest_Common_Divisor(int a,int b)  // Find the greatest common divisor 
{
    
    int temp,r;
    if(b>a)             // Let the larger of the two numbers be the dividend 
    {
    
        temp=a;
        a=b;
        b=temp;
    }
    while((r=a%b)!=0)
    {
    
        a=b;            // Divisor b Become a divisor a
        b=r;            // Make the remainder r Become a divisor b
    }
    return b;
}

int Least_Common_Multiple(int a,int b,int m)  // Find the least common multiple 
{
    
    return (a*b/m);
}

---

3. Running results