C Übungsbeispiele 16-- größte gemeinsame Teiler und kleinstes gemeinsames Vielfaches

100 Fälle von klassischen C - Sprache

Titel: Geben Sie zwei positive ganze Zahlen m und n, den größten gemeinsamen Teiler und kleinstes gemeinsames Vielfaches zu suchen.

Programmanalyse:

(1) Produkt = kleinste gemeinsame Vielfache von zwei Zahlen zusätzlich zu ihren gemeinsamen Nenner eingegeben, ist der Schlüssel, den gemeinsamen Nenner zu finden;

(2) größten gemeinsamen Teiler euklidische Algorithmus (auch als euklidische Algorithmus bekannt)

1) Beweis: Es sei c der größte gemeinsame Teiler von a und b, bezeichnet mit c = gcd (a, b), a> = b,
So = r a mod b
Sei a = kc, b = jc, dann k, sind j relativ prim, sonst c nicht der größte gemeinsame Teiler ist
Nach dem, r = a-mb = kc-mjc = (k-mj) c
R c ein Vielfaches zu sehen ist, und k-mj und j sind relativ prim, da sonst die oben genannten k, j coprime Widerspruch,
Es kann der größte gemeinsame Teiler c, das heißt, gcd (a, b) = gcd (b, a mod b), erwies sich gesehen, b und r werden.

2) Algorithmus Beschreibung:

Der erste Schritt: a ÷ b, so daß R ein Rest ist (0 ≤ r Schritt zwei: Swap: setzen einen ← b, b ← r und gibt den ersten Schritt.

Source Code:

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

Das obige Beispiel Ausgabe lautet:

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

100 Fälle von klassischen C - Sprache