程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> C練習實例 >> C 練習實例16 – 最大公約數和最小公倍數

C 練習實例16 – 最大公約數和最小公倍數

編輯:C練習實例

C 練習實例16 - 最大公約數和最小公倍數

題目:輸入兩個正整數m和n,求其最大公約數和最小公倍數。

程序分析:

(1)最小公倍數=輸入的兩個數之積除於它們的最大公約數,關鍵是求出最大公約數;

(2)求最大公約數用輾轉相除法(又名歐幾裡德算法)

1)證明:設c是a和b的最大公約數,記為c=gcd(a,b),a>=b,
令r=a mod b
設a=kc,b=jc,則k,j互素,否則c不是最大公約數
據上,r=a-mb=kc-mjc=(k-mj)c
可知r也是c的倍數,且k-mj與j互素,否則與前述k,j互素矛盾,
由此可知,b與r的最大公約數也是c,即gcd(a,b)=gcd(b,a mod b),得證。

2)算法描述:

第一步:a ÷ b,令r為所得余數(0≤r 第二步:互換:置 a←b,b←r,並返回第一步。

程序源代碼:

//  Created by www.runoob.com on 15/11/9.
//  Copyright © 2015年 菜鳥教程. All rights reserved.
//

#include<stdio.h>
int main()
{
    int a,b,t,r;
    printf("請輸入兩個數字:\n");
    scanf("%d %d",&a,&b);
    if(a<b)
    {t=b;b=a;a=t;}
    r=a%b;
    int n=a*b;
    while(r!=0)
    {
        a=b;
        b=r;
        r=a%b;
    }
    printf("這兩個數的最大公約數是%d,最小公倍數是%d\n",b,n/b);
    
    return 0;
}

以上實例輸出結果為:

請輸入兩個數字:
12 26
這兩個數的最大公約數是2,最小公倍數是156

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved