C-Übungsbeispiel 16 - Größter gemeinsamer Teiler und kleinstes gemeinsames Vielfaches

100 klassische C-Beispiele

Titel:Geben Sie zwei positive ganze Zahlen m und n ein und finden Sie ihren größten gemeinsamen Teiler und ihr kleinstes gemeinsames Vielfaches.

Programmanalyse:

(1) Kleinstes gemeinsames Vielfaches = das Produkt der beiden eingegebenen Zahlen geteilt durch ihren größten gemeinsamen Teiler; entscheidend ist, den größten gemeinsamen Teiler zu finden.

(2) Verwenden Sie den euklidischen Algorithmus (auch bekannt als euklidischer Algorithmus), um den größten gemeinsamen Teiler zu finden.

1) Beweis: Sei c der größte gemeinsame Teiler von a und b, bezeichnet als c = gcd(a, b), a >= b.
Sei r=a mod b
Seien a = kc, b = jc, dann sind k und j teilerfremd; andernfalls wäre c nicht der größte gemeinsame Teiler.
Aus dem Obigen folgt r=a-mb=kc-mjc=(k-mj)c
Man erkennt, dass r ebenfalls ein Vielfaches von c ist, und k - mj und j teilerfremd sind; andernfalls widerspricht dies der vorherigen Tatsache, dass k und j teilerfremd sind.
Somit erkennt man, dass der größte gemeinsame Teiler von b und r ebenfalls c ist, d. h. gcd(a,b)=gcd(b,a mod b). Bewiesen.

2) Algorithmusbeschreibung:

Schritt 1: a ÷ b, r sei der resultierende Rest (0 ≤ rSchritt 2: Vertauschen: Setzen Sie a←b, b←r und kehren Sie zu Schritt 1 zurück.

Beispiel

// Erstellt von www.example.com am 15/11/9. // Copyright © 2015 Example. Alle Rechte vorbehalten. // #include<stdio.h> int main() { int a,b,t,r,n; printf("Bitte geben Sie zwei Zahlen ein:\n"); scanf("%d %d",&a,&b); if(a<b) {t=b;b=a;a=t;} r=a%b; n=a*b; while(r!=0) { a=b; b=r; r=a%b; } printf("Der größte gemeinsame Teiler dieser beiden Zahlen ist %d, und das kleinste gemeinsame Vielfache ist %d\n",b,n/b); return 0; }

Die Ausgabe des obigen Beispiels ist:

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

100 klassische C-Beispiele

Weitere Erweiterungen