最大公約數(shù)：指能夠整除多個整數(shù)的最大正整數(shù)，而多個整數(shù)不能都為零。

最小公倍數(shù)：兩個或多個整數(shù)公有的倍數(shù)叫做它們的公倍數(shù)，其中除0以外最小的一個公倍數(shù)就叫做這幾個整數(shù)的最小公倍數(shù)。

求最小公倍數(shù)的算法：

最小公倍數(shù) = 兩個整數(shù)的乘積 / 最大公因數(shù)

求最大公約數(shù)的算法：

第一種方法：輾轉相除法

有兩個整數(shù)a和b:

1. a % b ==temp;

2. 若temp = 0；那么b就是最大公約數(shù)。

3. 若temp ≠ 0；則a = b；b = temp；繼續(xù)進行a % b 操作。

eg：求25和15的最大公約數(shù)，其過程為：

25 % 15 余 10 ； 15 % 10 余 5 ； 10 % 5 余 0 。因此5即為最大公約數(shù)

#include<stdio.h>
int main()
{
    int a  , b  , temp;
    printf("put in a and b : ");
    scanf("%d %d",&a,&b);
    int nul = a * b;
    
    while (a * b != 0)
    {
        temp = a % b;
        a = b;
        b = temp;
    }
    printf(" max = %d:",a);
    printf(" min = %d:", (nul / a)  );
    return 0;
}  

put in a and b : 25 15
 max = 5: min = 75:

第二種方法：相減法

取兩個整數(shù)a、b：

1. 若a > b,則 a = a - b；

2. 若a < b,則 b = b - a；

3. 若 a = b,則 a(b)即為兩數(shù)的最大公約數(shù)

4.若 a ≠ b,則繼續(xù)執(zhí)行第一步操作。

eg：求25和15的最大公約數(shù)，其過程為：

25 - 15 = 10(15 > 10);15 - 10 = 5(10 > 5);

10 - 5 = 5(5 == 5)

因此，25 和15的最大公約數(shù)為5。

代碼如下：

#include<stdio.h>
int main()
{
    int a , b , m , n;
    printf("put in a and b:");
    scanf("%d %d", &a, &b);
    m = a;
    n = b;
    while (a != b)
    {
        if(a > b)
        {
            a = a - b;
        }
        else
        {
            b = b - a;
        }
    }
    printf("max = %d\n", a);
    printf("min = %d",(m * n)/a);
    return 0;
}

運行結果展示：

put in a and b:25 15
max = 5
min = 75

第三種方法：窮舉法

有兩個整數(shù)a和b：

1. 令 i = 1，

2. 如果 a，b能同時被i整除，則h = i；

3. i++；

4. 若 i <= a(b)，則繼續(xù)執(zhí)行第2步操作；

5. 若i > a(b)，當 i = a(b)時，窮舉結束，則此時h即為最大公約數(shù)。

代碼如下

#include<stdio.h>
int main ()
{
    int a , b , m , n , i , h;
    printf("put in a and b:");
    scanf("%d %d", &a, &b);
    m = a;
    n = b;
    for( i = 1; i <= a; i ++)
    {
        if( a % i == 0 && b % i == 0)
        {
            h = i;
        }
    }
    printf("max = %d\n", h);
    printf("min = %d",(m * n) / h);
    return 0;
}

運行結果展示：文章來源地址http://www.zghlxwxcb.cn/news/detail-452360.html

put in a and b:25 15
max = 5
min = 75

到了這里，關于C語言 多種方法求最大公因數(shù)和最小公倍數(shù)的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！