Eine Ganzzahl in C in Primfaktoren zerlegen

Einführung

In diesem Lab werden Sie lernen, wie Sie eine Ganzzahl in ihre Primfaktoren zerlegen können, indem Sie ein C-Programm verwenden. Das Lab umfasst die folgenden Schritte:

1. Lesen Sie eine Ganzzahl als Eingabe vom Benutzer.
2. Implementieren Sie einen Algorithmus, um die Eingabezahl durch Primzahlen zu teilen, bis sie vollständig in Faktoren zerlegt ist.
3. Geben Sie die Primfaktoren der Eingabezahl aus.

Am Ende dieses Labs werden Sie ein besseres Verständnis für die Arbeit mit Ganzzahlen, Primzahlen und grundlegenden Programmierkonzepten in C haben.

Skills Graph

Einlesen einer Ganzzahl

In diesem Schritt werden Sie lernen, wie Sie in einem C-Programm zur Primfaktorzerlegung eine Ganzzahl als Eingabe vom Benutzer lesen können. Wir werden ein einfaches Programm erstellen, das den Benutzer auffordert, eine Zahl einzugeben und diese für die weitere Verarbeitung speichert.

Zuerst erstellen wir eine neue C-Datei im Verzeichnis ~/project:

cd ~/project
nano prime_factorization.c

Fügen Sie nun den folgenden Code hinzu, um eine Ganzzahl einzulesen:

#include <stdio.h>

int main() {
    int number;

    printf("Enter a positive integer to factorize: ");
    scanf("%d", &number);

    printf("You entered: %d\n", number);

    return 0;
}

Lassen Sie uns den Code analysieren:

• #include <stdio.h> inkludiert die Standard-Eingabe/Ausgabe-Bibliothek
• int main() ist die Hauptfunktion, in der die Programmausführung beginnt
• printf() wird verwendet, um dem Benutzer eine Eingabeaufforderung anzuzeigen
• scanf() liest die Ganzzahl-Eingabe vom Benutzer
• %d ist der Format-Spezifizierer für Ganzzahlen
• &number übergibt die Speicheradresse der Variablen number

Kompilieren und starten Sie das Programm:

gcc prime_factorization.c -o prime_factorization
./prime_factorization

Beispielausgabe:

Enter a positive integer to factorize: 24
You entered: 24

Durch Primzahlen teilen, bis vollständig in Faktoren zerlegt

In diesem Schritt werden Sie das vorherige Programm ändern, um den Algorithmus zur Primfaktorzerlegung zu implementieren. Wir werden die Datei prime_factorization.c aktualisieren, um die Eingabezahl durch Primzahlen zu teilen, bis sie vollständig in Faktoren zerlegt ist.

Öffnen Sie die vorhandene Datei:

cd ~/project
nano prime_factorization.c

Ersetzen Sie den vorherigen Code durch die folgende Implementierung:

#include <stdio.h>

void factorize(int number) {
    printf("Prime factors of %d: ", number);

    // Start with the smallest prime number
    for (int divisor = 2; divisor <= number; divisor++) {
        while (number % divisor == 0) {
            printf("%d ", divisor);
            number /= divisor;
        }
    }

    printf("\n");
}

int main() {
    int number;

    printf("Enter a positive integer to factorize: ");
    scanf("%d", &number);

    // Check for valid input
    if (number <= 1) {
        printf("Please enter a number greater than 1.\n");
        return 1;
    }

    factorize(number);

    return 0;
}

Lassen Sie uns den Algorithmus zur Primfaktorzerlegung analysieren:

• Die Funktion factorize() behandelt den Prozess der Primfaktorzerlegung
• Wir beginnen mit der kleinsten Primzahl (2)
• Die äußere for-Schleife versucht jeden potenziellen Teiler
• Die innere while-Schleife teilt die Zahl wiederholt durch den aktuellen Teiler
• Wir geben jeden Primfaktor aus, sobald wir ihn finden
• Die Zahl wird in jeder Iteration durch Ganzzahldivision aktualisiert

Kompilieren und starten Sie das Programm:

gcc prime_factorization.c -o prime_factorization
./prime_factorization

Beispielausgaben:

Enter a positive integer to factorize: 24
Prime factors of 24: 2 2 2 3

Enter a positive integer to factorize: 100
Prime factors of 100: 2 2 5 5

Ausgabe der Primfaktoren

In diesem Schritt werden Sie das Programm zur Primfaktorzerlegung erweitern, um eine detailliertere und formatierte Ausgabe der Primfaktoren zu liefern. Wir werden die vorhandene Datei prime_factorization.c ändern, um die Präsentation der Ergebnisse zu verbessern.

Öffnen Sie die Datei:

cd ~/project
nano prime_factorization.c

Aktualisieren Sie den Code mit einer verbesserten Faktorzerlegungsfunktion:

#include <stdio.h>

void factorize(int number) {
    int original_number = number;
    int factor_count = 0;

    printf("Prime Factorization of %d:\n", original_number);
    printf("---------------------\n");

    // Start with the smallest prime number
    for (int divisor = 2; divisor <= number; divisor++) {
        int current_factor_count = 0;
        while (number % divisor == 0) {
            number /= divisor;
            current_factor_count++;
            factor_count++;
        }

        // Print factors with their exponents
        if (current_factor_count > 0) {
            printf("%d^%d ", divisor, current_factor_count);
        }
    }

    printf("\n\nTotal number of prime factors: %d\n", factor_count);
}

int main() {
    int number;

    printf("Enter a positive integer to factorize: ");
    scanf("%d", &number);

    // Check for valid input
    if (number <= 1) {
        printf("Please enter a number greater than 1.\n");
        return 1;
    }

    factorize(number);

    return 0;
}

Wichtige Verbesserungen in dieser Version:

• Hinzufügen einer Formatierung zur Anzeige der Primfaktoren
• Anzeige des Exponenten jeder Primzahl
• Zählen der Gesamtzahl der Primfaktoren
• Beibehaltung der ursprünglichen Eingabezahl zur Anzeige

Kompilieren und starten Sie das Programm:

gcc prime_factorization.c -o prime_factorization
./prime_factorization

Beispielausgaben:

Enter a positive integer to factorize: 24
Prime Factorization of 24:
---------------------
2^3 3^1
Total number of prime factors: 4

Enter a positive integer to factorize: 100
Prime Factorization of 100:
---------------------
2^2 5^2
Total number of prime factors: 4

Zusammenfassung

In diesem Lab werden Sie lernen, wie Sie eine Ganzzahl als Eingabe vom Benutzer lesen, den Algorithmus zur Primfaktorzerlegung implementieren und die Primfaktoren der gegebenen Zahl ausgeben. Die wichtigsten Schritte umfassen das Lesen der Ganzzahl, das Teilen der Zahl durch Primzahlen, bis sie vollständig in Faktoren zerlegt ist, und das Ausgeben der Primfaktoren.

Das Programm fordert zunächst den Benutzer auf, eine positive Ganzzahl einzugeben, die dann in einer Variablen gespeichert wird. Der Algorithmus zur Primfaktorzerlegung wird in der Funktion factorize() implementiert, in der die Eingabezahl durch Primzahlen geteilt wird, bis sie vollständig in Faktoren zerlegt ist. Die Primfaktoren werden dann auf der Konsole ausgegeben.