Prüfen, ob eine Zahl Prim ist (C)

Einführung

In diesem Labor lernen wir, wie man in C-Programmierung prüft, ob eine Zahl prim ist. Das Labor besteht aus drei Schritten: das Einlesen einer ganzzahligen Eingabe vom Benutzer, die Prüfung der Teilbarkeit von 2 bis zur Quadratwurzel der Zahl und das Ausgeben, ob die Zahl prim ist oder nicht. Am Ende dieses Labors haben Sie ein funktionierendes Programm, das die Primheit einer gegebenen ganzen Zahl bestimmen kann.

Das Labor beginnt mit der Erklärung, wie man eine ganzzahlige Eingabe vom Benutzer mithilfe der Funktion scanf() liest. Anschließend wird der Algorithmus zur Prüfung von Primzahlen vorgestellt, der die Prüfung der Teilbarkeit von 2 bis zur Quadratwurzel der Eingabezahl beinhaltet. Wenn keine Teiler gefunden werden, gilt die Zahl als prim. Schließlich gibt das Programm das Ergebnis aus, das angibt, ob die Zahl prim ist oder nicht.

Eine Ganzzahl einlesen

In diesem Schritt lernen wir, wie man eine ganzzahlige Eingabe vom Benutzer in C-Programmierung liest. Dies ist der erste Schritt bei der Erstellung eines Primzahlprüfers.

Erstellen wir zunächst eine neue C-Datei für unser Primzahlprüfungsprogramm:

cd ~/project
nano prime_checker.c

Schreiben wir nun den Code zum Einlesen einer Ganzzahl:

#include <stdio.h>

int main() {
    int number;

    printf("Geben Sie eine positive ganze Zahl ein, um zu prüfen, ob sie prim ist: ");
    scanf("%d", &number);

    printf("Sie haben eingegeben: %d\n", number);

    return 0;
}

Beispielausgabe:

Geben Sie eine positive ganze Zahl ein, um zu prüfen, ob sie prim ist: 17
Sie haben eingegeben: 17

Zerlegen wir den Code:

• #include <stdio.h> inkludiert die Standard-Eingabe/Ausgabe-Bibliothek
• int main() ist die Hauptfunktion, in der der Programmstart erfolgt
• int number; deklariert eine Integer-Variable zur Speicherung der Benutzereingabe
• printf() zeigt eine Aufforderung an den Benutzer an
• scanf() liest eine ganzzahlige Eingabe vom Benutzer und speichert sie in number
• printf() bestätigt die vom Benutzer eingegebene Zahl

Kompilieren und ausführen des Programms:

gcc prime_checker.c -o prime_checker
./prime_checker

Teilbarkeitsprüfung von 2 bis √n

In diesem Schritt implementieren wir den Algorithmus zur Primzahlprüfung, indem wir die Teilbarkeit von 2 bis zur Quadratwurzel der Eingabezahl prüfen.

Ändern wir unser vorheriges C-Programm, um die Logik zur Primzahlprüfung hinzuzufügen:

nano ~/project/prime_checker.c

Aktualisieren Sie den Code mit der Teilbarkeitsprüfung:

#include <stdio.h>
#include <math.h>

int is_prime(int number) {
    // Zahlen kleiner als 2 sind keine Primzahlen
    if (number < 2) {
        return 0;
    }

    // Prüfung der Teilbarkeit von 2 bis zur Quadratwurzel der Zahl
    for (int i = 2; i <= sqrt(number); i++) {
        if (number % i == 0) {
            return 0; // Nicht prim, wenn teilbar
        }
    }

    return 1; // Prim, wenn keine Teiler gefunden wurden
}

int main() {
    int number;

    printf("Geben Sie eine positive ganze Zahl ein, um zu prüfen, ob sie prim ist: ");
    scanf("%d", &number);

    if (is_prime(number)) {
        printf("%d ist eine Primzahl.\n", number);
    } else {
        printf("%d ist keine Primzahl.\n", number);
    }

    return 0;
}

Kompilieren Sie das Programm mit der Mathematikbibliothek:

gcc ~/project/prime_checker.c -o ~/project/prime_checker -lm

Beispielausgaben:

Geben Sie eine positive ganze Zahl ein, um zu prüfen, ob sie prim ist: 17
17 ist eine Primzahl.

Geben Sie eine positive ganze Zahl ein, um zu prüfen, ob sie prim ist: 20
20 ist keine Primzahl.

Wichtige Punkte zur Implementierung:

• Die Funktion sqrt() aus <math.h> berechnet die Quadratwurzel.
• Wir prüfen die Teilbarkeit nur bis zu √n, um den Algorithmus zu optimieren.
• Wenn keine Teiler gefunden werden, ist die Zahl prim.
• Der Modulo-Operator % prüft die Teilbarkeit.
• Wir geben 0 für keine Primzahl und 1 für Primzahlen zurück.

Ausgabe, ob Primzahl oder nicht

In diesem letzten Schritt erweitern wir unser Primzahlprüfungsprogramm, indem wir detailliertere Ausgaben hinzufügen und die Überprüfung mehrerer Zahlen ermöglichen.

Ändern wir das Programm, um umfassendere Ausgaben zu liefern:

nano ~/project/prime_checker.c

Aktualisieren Sie den Code mit einer verbesserten Benutzeroberfläche:

#include <stdio.h>
#include <math.h>

int is_prime(int number) {
    // Zahlen kleiner als 2 sind keine Primzahlen
    if (number < 2) {
        return 0;
    }

    // Prüfung der Teilbarkeit von 2 bis zur Quadratwurzel der Zahl
    for (int i = 2; i <= sqrt(number); i++) {
        if (number % i == 0) {
            return 0; // Nicht prim, wenn teilbar
        }
    }

    return 1; // Prim, wenn keine Teiler gefunden wurden
}

void print_prime_details(int number) {
    if (is_prime(number)) {
        printf("%d ist eine PRIMZAHL!\n", number);
        printf("Erklärung:\n");
        printf("- Sie ist nur durch 1 und sich selbst teilbar\n");
        printf("- Zwischen 2 und √%d wurden keine weiteren Teiler gefunden\n", number);
    } else {
        printf("%d ist KEINE Primzahl.\n", number);

        // Suche und Ausgabe des kleinsten Teilers
        for (int i = 2; i <= sqrt(number); i++) {
            if (number % i == 0) {
                printf("Erklärung:\n");
                printf("- Teilbar durch %d\n", i);
                printf("- %d × %d = %d\n", i, number / i, number);
                break;
            }
        }
    }
}

int main() {
    int number, continue_check;

    do {
        printf("Geben Sie eine positive ganze Zahl ein, um zu prüfen, ob sie prim ist: ");
        scanf("%d", &number);

        print_prime_details(number);

        printf("\nMöchten Sie eine weitere Zahl prüfen? (1=Ja, 0=Nein): ");
        scanf("%d", &continue_check);
    } while (continue_check == 1);

    printf("Vielen Dank für die Nutzung des Primzahlprüfers!\n");

    return 0;
}

Kompilieren Sie das Programm:

gcc ~/project/prime_checker.c -o ~/project/prime_checker -lm

Beispielausgaben:

Geben Sie eine positive ganze Zahl ein, um zu prüfen, ob sie prim ist: 17
17 ist eine PRIMZAHL!
Erklärung:
- Sie ist nur durch 1 und sich selbst teilbar
- Zwischen 2 und √17 wurden keine weiteren Teiler gefunden

Möchten Sie eine weitere Zahl prüfen? (1=Ja, 0=Nein): 1

Geben Sie eine positive ganze Zahl ein, um zu prüfen, ob sie prim ist: 20
20 ist KEINE Primzahl.
Erklärung:
- Teilbar durch 2
- 2 × 10 = 20

Möchten Sie eine weitere Zahl prüfen? (1=Ja, 0=Nein): 0
Vielen Dank für die Nutzung des Primzahlprüfers!

Wichtige Verbesserungen:

• Detaillierte Erklärungen für Prim- und Nicht-Primzahlen hinzugefügt
• Implementierung einer Schleife für die Überprüfung mehrerer Zahlen
• Bereitstellung aussagekräftigerer Ausgaben über Eigenschaften der Zahlen

Zusammenfassung

In diesem Labor haben wir gelernt, wie man eine ganzzahlige Eingabe vom Benutzer in C liest, was der erste Schritt bei der Erstellung eines Primzahlprüfers ist. Anschließend haben wir den Algorithmus zur Primzahlprüfung implementiert, indem wir die Teilbarkeit von 2 bis zur Quadratwurzel der Eingabezahl geprüft haben. Das Programm prüft, ob eine gegebene Zahl prim ist, indem es die Zahlen von 2 bis zur Quadratwurzel der Zahl durchläuft und prüft, ob eine von ihnen die Zahl ohne Rest teilt. Wenn keine Teiler gefunden werden, gilt die Zahl als prim.