C-Übungsbeispiel 33 - Primzahlbestimmung

100 klassische C-Beispiele

Titel:Bestimmen Sie, ob eine Zahl eine Primzahl ist.

Programmanalyse:Primzahlen, auch Primzahlen genannt, gibt es unendlich viele. Eine natürliche Zahl größer als 1, die durch keine andere natürliche Zahl außer 1 und sich selbst geteilt werden kann.

Programmquellcode:

Beispiel

#include<stdio.h> #include<math.h> #define MAX 1000 // Maximale Arraygröße int prime[MAX]; // Array zum Speichern, ob es eine Primzahl ist // Einfache Methode zur Bestimmung, ob eine Zahl eine Primzahl ist (Brute-Force) int isPrimeNaive(int n) { if (n <= 1) // Zahlen kleiner oder gleich 1 sind keine Primzahlen return 0; for (int i = 2; i < n; i++) // Prüfe der Reihe nach von 2 bis n-1, ob sie n teilen if (n % i == 0) // Wenn es ohne Rest teilbar ist, ist es keine Primzahl return 0; return 1; // Wenn kein Faktor gefunden wird, ist sie eine Primzahl } // Optimierte Primzahlprüfung: nur bis sqrt(n) prüfen und gerade Zahlen überspringen int isPrime(int n) { if (n <= 1) // Zahlen kleiner oder gleich 1 sind keine Primzahlen return 0; if (n == 2) // 2 ist eine Primzahl return 1; if (n % 2 == 0) // Gerade Zahlen ausschließen return 0; int limit = (int)sqrt((double)n); // Es muss nur bis sqrt(n) geprüft werden for (int i = 3; i <= limit; i += 2) // Bei 3 beginnen und nur ungerade Zahlen prüfen { if (n % i == 0) // Wenn es ohne Rest teilbar ist, ist es keine Primzahl return 0; } return 1; // Alle Tests bestanden, n ist eine Primzahl } // Sieb-Initialisierung: Primzahltabelle erstellen void sieve() { for (int i = 0; i < MAX; i++) prime[i] = 1; // Angenommen, alle Zahlen sind Primzahlen prime[0] = prime[1] = 0; // 0 und 1 sind keine Primzahlen int limit = (int)sqrt((double)MAX); // Nur bis sqrt(MAX) prüfen for (int i = 2; i <= limit; i++) // Beginne bei 2 und durchlaufe jede Zahl { if (prime[i]) // Wenn i eine Primzahl ist { for (int j = i * i; j < MAX; j += i) // Markiere Vielfache von i als nicht prim prime[j] = 0; } } } // Ermittle mit dem Siebverfahren, ob eine Zahl prim ist int isPrimeSieve(int n) { return prime[n]; // Gib direkt zurück, ob dieser Index eine Primzahl ist } int main() { sieve(); // Primzahlsieb initialisieren // Teste verschiedene Zahlen, um zu sehen, ob sie Primzahlen sind printf("N=%d %d\n", 1, isPrime(1)); // Ausgabe: 1 ist keine Primzahl printf("N=%d %d\n", 2, isPrime(2)); // Ausgabe: 2 ist eine Primzahl printf("N=%d %d\n", 3, isPrime(3)); // Ausgabe: 3 ist eine Primzahl printf("N=%d %d\n", 4, isPrime(4)); // Ausgabe: 4 ist keine Primzahl printf("N=%d %d\n", 7, isPrime(7)); // Ausgabe: 7 ist eine Primzahl printf("N=%d %d\n", 9, isPrime(9)); // Ausgabe: 9 ist keine Primzahl printf("N=%d %d\n", 13, isPrime(13)); // Ausgabe: 13 ist eine Primzahl printf("N=%d %d\n", 17, isPrime(17)); // Ausgabe: 17 ist eine Primzahl printf("N=%d %d\n", 100, isPrime(100)); // Ausgabe: 100 ist keine Primzahl printf("N=%d %d\n", 23, isPrime(23)); // Ausgabe: 23 ist eine Primzahl printf("N=%d %d\n", 1, isPrime(1)); // Ausgabe: 1 ist keine Primzahl return 0; }

Das Ausgabeergebnis des obigen Beispiels ist (eine nachgestellte Ziffer von 1 kennzeichnet eine Primzahl, 0 kennzeichnet keine Primzahl):

N=1 0
N=2 1
N=3 1
N=4 0
N=7 1
N=9 0
N=13 1
N=17 1
N=100 0
N=23 1
N=1 0

100 klassische C-Beispiele

Weitere Erweiterungen