C-Übungsbeispiel 16 - Größter gemeinsamer Teiler und kleinstes gemeinsames Vielfaches
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
Die Ausgabe des obigen Beispiels ist:
请输入两个数字: 12 26 这两个数的最大公约数是2,最小公倍数是156Weitere Erweiterungen