Deutsche Lernausgabe
Primzahlen in C
Prüfen Sie Teiler bis zur Quadratwurzel und behandeln Sie Werte unter zwei korrekt.
Eine Primzahl ist eine Ganzzahl größer als eins mit genau zwei positiven Teilern. Null, eins und negative Zahlen sind nicht prim. Eine zusammengesetzte Zahl besitzt mindestens einen Faktor höchstens gleich ihrer Quadratwurzel.
Schließen Sie gerade Zahlen außer zwei aus und prüfen Sie ungerade Teiler. Bei großen positiven Werten verhindert divisor <= N / divisor einen Überlauf von divisor * divisor. Stoppen Sie, sobald ein exakter Teiler gefunden ist.
Testen Sie 1, 2, ein Quadrat wie 49 und eine Primzahl. Probedivision benötigt O(sqrt(N)) Zeit und O(1) Hilfsspeicher.
Quellcode
#include <stdio.h>
#include <stdbool.h>
bool is_prime_optimized(int n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
// Check factors 6k +/- 1 up to sqrt(n)
for (int i = 5; (long long)i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) {
return false;
}
}
return true;
}
int main(void) {
int test_numbers[] = {1, 2, 17, 25, 29, 49, 97, 100};
int total = sizeof(test_numbers) / sizeof(test_numbers[0]);
printf("--- Prime Number Verification ---\n");
for (int i = 0; i < total; i++) {
int val = test_numbers[i];
printf("%3d -> %s\n", val, is_prime_optimized(val) ? "PRIME" : "NOT prime");
}
printf("\nPrimes between 1 and 50:\n");
for (int i = 1; i <= 50; i++) {
if (is_prime_optimized(i)) {
printf("%d ", i);
}
}
printf("\n");
return 0;
}Erwartetes Ergebnis
--- Prime Number Verification --- 1 -> NOT prime 2 -> PRIME 17 -> PRIME 25 -> NOT prime 29 -> PRIME 49 -> NOT prime 97 -> PRIME 100 -> NOT prime Primes between 1 and 50: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
Häufige Fragen
Warum bleiben Code und manche Ausgaben englisch?
C-Schlüsselwörter, Bezeichner, Programmkommentare und erwartete Ausgaben bleiben wie im Original, damit der Code ausführbar und die Tests konsistent bleiben. Erklärungen und Aufgabenstellungen sind übersetzt.