ตัวอย่างการใช้สิทธิ C 16-- ตัวหารร่วมมากและตัวคูณร่วมน้อย

100 กรณีของภาษา C คลาสสิก

ชื่อเรื่อง: ใส่จำนวนเต็มบวก n และ m ที่กำลังมองหาตัวหารร่วมมากและตัวคูณร่วมน้อย

การวิเคราะห์โครงการ:

(1) สินค้า = ตัวคูณร่วมน้อยของตัวเลขสองเข้ามานอกเหนือจากการหารร่วมของพวกเขาที่สำคัญคือการหาตัวหารร่วม;

(2) ตัวหารร่วมมากโดยใช้ขั้นตอนวิธี Euclidean (หรือเรียกว่าขั้นตอนวิธี Euclidean)

1) มีหลักฐาน: Let C เป็นตัวหารที่ยิ่งใหญ่ที่สุดที่พบบ่อยของ A และ B แสดงโดย c = GCD (A, B) ซึ่งเป็น> = B,
ดังนั้น r = พอควร B
ให้ A = KC, B = JC แล้ว K, J มีความสำคัญมิฉะนั้น C ไม่ได้เป็นตัวหารร่วมมาก
ตามที่, R = A-MB = KC-MJC = (K-MJ) C
R C จะเห็นหลายและ K-MJ และ J มีความสำคัญเป็นอย่างอื่นดังกล่าว K, J coprime ขัดแย้ง
มันสามารถเห็นได้, B และ R เป็นที่ยิ่งใหญ่ที่สุด C หารกันเช่น GCD (A, B) = GCD (B, พอควรข) ได้รับการพิสูจน์

2) คำอธิบายขั้นตอนวิธีการ:

ขั้นตอนแรก: การ÷ B ดังนั้น R ที่เป็นส่วนที่เหลือ (0≤r ขั้นตอนที่สอง: Swap: ตั้ง← B, B ← R และผลตอบแทนขั้นตอนแรก

รหัสที่มา:

//  Created by www.w3big.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

100 กรณีของภาษา C คลาสสิก