Kleinstes gemeinsames Vielfaches (LCM) in C berechnen

Einführung

In diesem Lab lernen Sie, wie man den kleinsten gemeinsamen Vielfachen (LCM) zweier ganzer Zahlen mit C programmieren kann. Das Lab deckt den schrittweisen Prozess ab, beginnend mit der Eingabe zweier ganzer Zahlen vom Benutzer, dann der Implementierung der Formel LCM = (a*b)/GCD(a,b) zur Berechnung des LCM und schließlich der Ausgabe des Ergebnisses. Am Ende dieses Labs haben Sie ein solides Verständnis dafür, wie Sie Konzepte der Zahlentheorie, wie den euklidischen Algorithmus zur Berechnung des größten gemeinsamen Teilers (GCD), anwenden, um praktische Probleme in C zu lösen.

Zwei ganze Zahlen einlesen

In diesem Schritt lernen Sie, wie Sie zwei ganze Zahlen als Benutzereingabe in C einlesen, der erste Schritt zur Berechnung des kleinsten gemeinsamen Vielfachen (LCM).

Erstellen Sie zunächst eine neue C-Datei für unser LCM-Programm:

cd ~/project
nano lcm.c

Fügen Sie nun den folgenden Code hinzu, um zwei ganze Zahlen einzulesen:

#include <stdio.h>

int main() {
    int a, b;

    printf("Geben Sie zwei positive ganze Zahlen ein:\n");
    printf("Erste Zahl: ");
    scanf("%d", &a);

    printf("Zweite Zahl: ");
    scanf("%d", &b);

    printf("Sie haben eingegeben: %d und %d\n", a, b);

    return 0;
}

Kompilieren und führen Sie das Programm aus:

gcc lcm.c -o lcm
./lcm

Beispielausgabe:

Geben Sie zwei positive ganze Zahlen ein:
Erste Zahl: 12
Zweite Zahl: 18
Sie haben eingegeben: 12 und 18

Zerlegung des Codes:

Die Funktion scanf() wird verwendet, um ganzzahlige Eingaben vom Benutzer zu lesen.
Der Formatbezeichner %d wird für die ganzzahlige Eingabe verwendet.
&a und &b übergeben die Speicheradressen, in denen die Eingabewerte gespeichert werden.

LCM = (a*b)/GCD(a,b) verwenden

In diesem Schritt implementieren Sie die Berechnung des kleinsten gemeinsamen Vielfachen (LCM) mithilfe der Formel LCM(a,b) = (a*b)/GCD(a,b). Zuerst erstellen wir eine Funktion zur Berechnung des größten gemeinsamen Teilers (GCD) mithilfe des euklidischen Algorithmus.

Aktualisieren Sie die Datei lcm.c mit folgendem Code:

#include <stdio.h>

// Funktion zur Berechnung des GCD mit dem euklidischen Algorithmus
int calculateGCD(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// Funktion zur Berechnung des LCM
int calculateLCM(int a, int b) {
    return (a * b) / calculateGCD(a, b);
}

int main() {
    int a, b, lcm;

    printf("Geben Sie zwei positive ganze Zahlen ein:\n");
    printf("Erste Zahl: ");
    scanf("%d", &a);

    printf("Zweite Zahl: ");
    scanf("%d", &b);

    lcm = calculateLCM(a, b);

    printf("Das kleinste gemeinsame Vielfache von %d und %d ist: %d\n", a, b, lcm);

    return 0;
}

Kompilieren und ausführen des Programms:

gcc lcm.c -o lcm
./lcm

Beispielausgabe:

Geben Sie zwei positive ganze Zahlen ein:
Erste Zahl: 12
Zweite Zahl: 18
Das kleinste gemeinsame Vielfache von 12 und 18 ist: 36

Zerlegung der Schlüsselkomponenten:

calculateGCD() implementiert den euklidischen Algorithmus zur Berechnung des größten gemeinsamen Teilers.
calculateLCM() verwendet die Formel LCM(a,b) = (a*b)/GCD(a,b).
Der euklidische Algorithmus findet den GCD effizient, indem er wiederholt den Rest berechnet.

Ausgabe des LCM

In diesem letzten Schritt führen Sie das LCM-Programm aus und überprüfen die Ausgabe für verschiedene Eingabekombinationen. Wir testen das Programm mit verschiedenen ganzzahligen Paaren, um die LCM-Berechnung zu demonstrieren.

Kompilieren Sie das Programm (falls noch nicht kompiliert):

cd ~/project
gcc lcm.c -o lcm

Führen Sie das Programm mit verschiedenen Eingabekombinationen aus:

./lcm << EOF
12
18
EOF

Beispielausgabe für 12 und 18:

Geben Sie zwei positive ganze Zahlen ein:
Erste Zahl: 12
Zweite Zahl: 18
Das kleinste gemeinsame Vielfache von 12 und 18 ist: 36

Probieren wir ein weiteres Beispiel:

./lcm << EOF
15
25
EOF

Beispielausgabe für 15 und 25:

Geben Sie zwei positive ganze Zahlen ein:
Erste Zahl: 15
Zweite Zahl: 25
Das kleinste gemeinsame Vielfache von 15 und 25 ist: 75

Wichtige Punkte:

Das LCM ist die kleinste positive ganze Zahl, die durch beide Eingabezahlen teilbar ist.
Für 12 und 18 ist das LCM 36.
Für 15 und 25 ist das LCM 75.
Das Programm verwendet die Formel LCM(a,b) = (a*b)/GCD(a,b).

Um das Programm robuster zu gestalten, können Sie eine Eingabevalidierung hinzufügen:

nano lcm.c

Aktualisieren Sie die Funktion main(), um die Eingabevalidierung einzubeziehen:

int main() {
    int a, b, lcm;

    printf("Geben Sie zwei positive ganze Zahlen ein:\n");
    printf("Erste Zahl: ");
    scanf("%d", &a);

    printf("Zweite Zahl: ");
    scanf("%d", &b);

    // Eingabevalidierung
    if (a <= 0 || b <= 0) {
        printf("Fehler: Bitte geben Sie nur positive ganze Zahlen ein.\n");
        return 1;
    }

    lcm = calculateLCM(a, b);

    printf("Das kleinste gemeinsame Vielfache von %d und %d ist: %d\n", a, b, lcm);

    return 0;
}

Überprüfen und testen Sie das aktualisierte Programm:

gcc lcm.c -o lcm
./lcm

Zusammenfassung

In diesem Labor lernen Sie, wie man das kleinste gemeinsame Vielfache (LCM) zweier ganzer Zahlen in der C-Programmierung berechnet. Zuerst lesen Sie zwei ganze Zahlen von der Benutzereingabe. Anschließend implementieren Sie die Formel LCM(a,b) = (a*b)/GCD(a,b), indem Sie eine Funktion erstellen, die den größten gemeinsamen Teiler (GCD) mithilfe des euklidischen Algorithmus berechnet. Schließlich geben Sie das berechnete LCM aus.

Die wichtigsten Lernpunkte sind: das Lesen ganzzahliger Eingaben mit scanf(), die Implementierung des euklidischen Algorithmus zur Berechnung des GCD und die Verwendung der Formel zur Berechnung des LCM. Am Ende dieses Labors haben Sie ein solides Verständnis dafür, wie man das LCM zweier Zahlen in C berechnet.