C-Übungsbeispiel 33 - Primzahlbestimmung
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 0Weitere Erweiterungen