Przykłady C Ćwiczenia 16-- największy wspólny dzielnik i najmniejszą wspólną wielokrotność

100 przypadki klasycznego języka C

Tytuł: Podaj dwie liczby całkowite dodatnie m i n, szukając największy wspólny dzielnik i najmniejszą wspólną wielokrotność.

Analiza Program:

(1) Produkt = najmniejszą wspólną wielokrotność dwóch liczb wpisanych w uzupełnieniu do ich wspólnego mianownika, kluczem jest znalezienie wspólnego mianownika;

(2) największy wspólny dzielnik za pomocą algorytmu Euklidesa (znany również jako algorytm Euklidesa)

1) Dowód: Niech c jest największy wspólny dzielnik a i b, oznaczamy przez C = NWD (a, b), a> = b,
Tak więc r = a mod b
Niech = Kc, b = JC następnie k, j są względnie pierwsze, inaczej C nie jest największy wspólny dzielnik
Według r = a-mb = KC-mjc = (k-mj) c
Rc jest postrzegana wielokrotności i K-mj oraz j są liczbami względnie pierwszymi, poza ww k, j względnie pierwsze sprzeczność,
Można zauważyć, b, r jest największy wspólny dzielnik C, czyli GCD (a, b) = GCD (b, mod b), okazało się.

2) opis algorytmu:

Pierwszy krok: a ÷ b tak, że r jest pozostała (0≤r Krok drugi: Zmienne: ustawić ← B, B ← r, i zwraca pierwszy krok.

Kod źródłowy:

//  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;
}

Powyższy przykład wyjście jest:

请输入两个数字：
12 26
这两个数的最大公约数是2，最小公倍数是156

100 przypadki klasycznego języka C