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.
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
%dveranlasstscanf(), 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.
