What are the greatest common divisor and least common multiple?

Greatest common divisor: refers to the largest positive integer that can divide multiple integers, and multiple integers cannot all be zero. For example, the greatest common divisor of 8 and 12 is 4;

Least common multiple:The common multiples of two or more integers are called their common multiples. The smallest common multiple other than 0 is called the least common multiple of these integers, such as the smallest of 6 and 24. The common multiple is 24.

Demonstration case:

C language calculates two Methods for the greatest common divisor and least common multiple of numbers:

1. Calculate the greatest common divisor of two numbers

According to the definition of divisors, it can be seen that all divisors of a certain number must not be greater than the number itself, and the greatest common divisor of several natural numbers must not be greater than any one of them. To find the greatest common divisor of any two positive integers is to find the largest natural number that is not larger than either of the two but can divide both integers at the same time.

Algorithm idea: Find the first number that can divide two integers at the same time in order from large (the smaller of the two integers) to small (to the smallest integer 1) The natural number is what you want.

Code example:

#include<stdio.h>
int main()
{
    int m, n, temp, i;
    printf("请输入任意2个数:\n");
    scanf("%d%d", &m, &n);
    if(m<n)  /*比较大小，使得m中存储大数，n中存储小数*/
    { /*交换m和n的值*/
        temp=m;
        m=n;
        n=temp;
    }
    for(i=n; i>0; i--)  /*按照从大到小的顺序寻找满足条件的自然数*/
        if(m%i==0 && n%i==0)
        {/*输出满足条件的自然数并结束循环*/
            printf("%d 和 %d 的最大公约数为: %d\n", m, n, i);
            break;
        }
   
    return 0;
}

Output:

##2. Calculate the least common multiple of two numbers

Idea: Find the least common multiple of any two positive integers, that is, find the smallest natural number that can be divided by two integers at the same time.

Code example:

#include<stdio.h>
int main()
{
    int m, n, temp, i;
    printf("请输入任意2个数:\n");
    scanf("%d%d", &m, &n);
    if(m<n)  /*比较大小，使得m中存储大数，n中存储小数*/
    { /*交换m和n的值*/
        temp=m;
        m=n;
        n=temp;
    }
    for(i=m; i>0; i++)  /*从大数开始寻找满足条件的自然数*/
        if(i%m==0 && i%n==0)
        {/*输出满足条件的自然数并结束循环*/
            printf("%d 和 %d 的最小公倍数为: %d\n", m, n, i);
            break;
        }
   
    return 0;
}

Output:

The least common multiple can also be found using the greatest common divisor, formula:

●　Least common multiple = product of two numbers/greatest common (factor) number

The above is the entire content of this article, I hope it will be helpful to everyone's study. For more exciting content, you can pay attention to the relevant tutorial columns of the PHP Chinese website! ! !

Related learning recommendations:

C video tutorial

The above is the detailed content of What are the greatest common divisor and least common multiple?. For more information, please follow other related articles on the PHP Chinese website!