Implementiere das Sieb des Eratosthenes in C

Einführung

In diesem Lab lernst du, wie du den Sieb des Eratosthenes-Algorithmus in C implementierst, um Primzahlen bis zu einer vorgegebenen Obergrenze zu finden. Du wirst beginnen, die Obergrenze von der Benutzerschaft einzulesen, dann die Vielfachen von Primzahlen als nicht-prim markieren und schließlich alle gefundenen Primzahlen ausdrucken. Dieses Lab behandelt Konzepte der Zahlentheorie und der diskreten Mathematik unter Verwendung der C-Programmiersprache.

Das Lab besteht aus drei Hauptschritten: das Einlesen der Obergrenze, das Markieren von Vielfachen als nicht-prim und das Ausdrucken aller Primzahlen. Indem du diesen Schritten folgst, wirst du ein tieferes Verständnis des Sieb des Eratosthenes-Algorithmus und seiner Implementierung in C gewinnen.

Skills Graph

Obergrenze einlesen

In diesem Schritt lernst du, wie du die Obergrenze für den Sieb des Eratosthenes-Algorithmus in C einliest. Die Obergrenze bestimmt den Bereich der Primzahlen, die wir finden möchten.

Zunächst erstellen wir eine neue C-Datei für unsere Implementierung:

cd ~/project
nano prime_sieve.c

Nun schreiben wir den Anfangscode, um die Obergrenze einzulesen:

#include <stdio.h>

int main() {
    int upper_limit;

    printf("Geben Sie die Obergrenze für die Suche nach Primzahlen ein: ");
    scanf("%d", &upper_limit);

    printf("Eingegebene Obergrenze: %d\n", upper_limit);

    return 0;
}

Kompilieren und ausführen des Programms:

gcc prime_sieve.c -o prime_sieve
./prime_sieve

Beispielausgabe:

Geben Sie die Obergrenze für die Suche nach Primzahlen ein: 50
Eingegebene Obergrenze: 50

Zergliedern wir den Code:

• Wir verwenden scanf(), um eine ganzzahlige Eingabe von der Benutzerschaft zu lesen
• Der Formatzeichen %d veranlasst scanf(), eine Ganzzahl zu lesen
• Wir speichern die Eingabe in der Variable upper_limit
• Anschließend drucken wir die eingegebene Obergrenze aus, um die Eingabe zu bestätigen

Vielfache als nicht-prim markieren

In diesem Schritt implementierst du die Kernlogik des Sieb des Eratosthenes-Algorithmus, um die Vielfachen von Primzahlen als nicht-prim zu markieren.

Ändern wir die vorherige prime_sieve.c-Datei:

cd ~/project
nano prime_sieve.c

Aktualisieren Sie den Code, um ein Array hinzuzufügen und die Vielfachen zu markieren:

#include <stdio.h>
#include <stdbool.h>

int main() {
    int upper_limit;

    printf("Geben Sie die Obergrenze für die Suche nach Primzahlen ein: ");
    scanf("%d", &upper_limit);

    // Erstellen Sie ein bool'sches Array, um Prim- und Nicht-Primzahlen zu markieren
    bool is_prime[upper_limit + 1];

    // Initialisieren Sie alle Zahlen als prim
    for (int i = 2; i <= upper_limit; i++) {
        is_prime[i] = true;
    }

    // Markieren Sie die Vielfachen jeder Primzahl als nicht-prim
    for (int p = 2; p * p <= upper_limit; p++) {
        if (is_prime[p]) {
            // Markieren Sie die Vielfachen von p als nicht-prim
            for (int i = p * p; i <= upper_limit; i += p) {
                is_prime[i] = false;
            }
        }
    }

    printf("Markieren der Vielfachen abgeschlossen.\n");

    return 0;
}

Kompilieren und ausführen des Programms:

gcc prime_sieve.c -o prime_sieve
./prime_sieve

Beispielausgabe:

Geben Sie die Obergrenze für die Suche nach Primzahlen ein: 50
Markieren der Vielfachen abgeschlossen.

Zergliedern wir die Logik des Sieb des Eratosthenes:

• Wir erstellen ein bool'sches Array is_prime, um Prim- und Nicht-Primzahlen zu verfolgen
• Am Anfang werden alle Zahlen als prim markiert
• Wir iterieren durch die Zahlen von 2 bis sqrt(Obergrenze)
• Für jede Primzahl markieren wir ihre Vielfachen als nicht-prim
• Wir beginnen mit p^2, um den Algorithmus zu optimieren
• Die innere Schleife erhöht sich um p, um alle Vielfachen von p zu markieren

Alle Primzahlen ausdrucken

In diesem Schritt vervollständigen Sie die Implementierung des Sieb des Eratosthenes, indem Sie alle innerhalb des angegebenen Bereichs gefundenen Primzahlen ausdrucken.

Ändern wir die prime_sieve.c-Datei, um die Ausdruckfunktionalität hinzuzufügen:

cd ~/project
nano prime_sieve.c

Aktualisieren Sie den Code, um Primzahlen auszudrucken:

#include <stdio.h>
#include <stdbool.h>

int main() {
    int upper_limit;

    printf("Geben Sie die Obergrenze für die Suche nach Primzahlen ein: ");
    scanf("%d", &upper_limit);

    // Erstellen Sie ein bool'sches Array, um Prim- und Nicht-Primzahlen zu markieren
    bool is_prime[upper_limit + 1];

    // Initialisieren Sie alle Zahlen als prim
    for (int i = 2; i <= upper_limit; i++) {
        is_prime[i] = true;
    }

    // Markieren Sie die Vielfachen jeder Primzahl als nicht-prim
    for (int p = 2; p * p <= upper_limit; p++) {
        if (is_prime[p]) {
            // Markieren Sie die Vielfachen von p als nicht-prim
            for (int i = p * p; i <= upper_limit; i += p) {
                is_prime[i] = false;
            }
        }
    }

    // Drucken Sie alle Primzahlen
    printf("Primzahlen bis zu %d sind:\n", upper_limit);
    for (int p = 2; p <= upper_limit; p++) {
        if (is_prime[p]) {
            printf("%d ", p);
        }
    }
    printf("\n");

    return 0;
}

Kompilieren und ausführen des Programms:

gcc prime_sieve.c -o prime_sieve
./prime_sieve

Beispielausgabe:

Geben Sie die Obergrenze für die Suche nach Primzahlen ein: 50
Primzahlen bis zu 50 sind:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Zergliedern wir die letzten Schritte:

• Nachdem die Vielfachen markiert wurden, iterieren wir durch das is_prime-Array
• Wir drucken nur die Zahlen aus, die weiterhin als prim markiert sind
• Die Ausgabe zeigt alle Primzahlen bis zur vom Benutzer angegebenen Obergrenze an

Zusammenfassung

In diesem Lab hast du zunächst gelernt, wie du die Obergrenze für den Sieb des Eratosthenes-Algorithmus in C einliest. Du hast eine C-Datei, prime_sieve.c, erstellt und Code geschrieben, um den Benutzer nach der Obergrenze zu fragen und sie in der Variable upper_limit zu speichern. Anschließend hast du die Kernlogik des Sieb des Eratosthenes-Algorithmus implementiert, indem du ein bool'sches Array erstellt hast, um Prim- und Nicht-Primzahlen zu markieren. Du hast alle Zahlen als prim initialisiert und dann die Vielfachen jeder Primzahl als nicht-prim markiert. Schließlich wirst du lernen, wie du alle Primzahlen innerhalb der angegebenen Obergrenze ausdrucken.