CKTIS / C
Primzahltest durch Probedivision
Prüfe, ob eine ganze Zahl eine Primzahl ist, indem du mögliche Teiler nur bis zu ihrer Quadratwurzel testest. In C prüft die Bedingung `d <= n / d` diese Grenze ohne das Überlaufrisiko einer Multiplikation.
Version: C23; repository compiler flag, production runtime not attested
Syntax
for (int d = 3; d <= n / d; d += 2) { if (n % d == 0) return 0; }Der Primzahltest durch Probedivision prüft, ob n außer 1 und n noch einen Teiler hat. Verwirf zuerst n < 2, akzeptiere n == 2 und verwirf alle anderen geraden Zahlen. Prüfe für die übrigen Kandidaten nur ungerade d ab 3. Gilt n % d == 0, ist die Zahl zusammengesetzt. Findet die Schleife keinen Teiler, ist die Zahl eine Primzahl.
Teiler treten paarweise auf: Wenn n = a * b gilt und beide Faktoren größer als 1 sind, ist mindestens einer von ihnen höchstens so groß wie die Quadratwurzel von n. Die Grenze zählt mit: Für 49 muss die Schleife auch 7 prüfen.
Verwende d <= n / d statt d * d <= n, um die Teilergrenze ohne Überlauf zu prüfen. Bei positiven n und d rundet die Ganzzahldivision in C den Quotienten ab, daher sind beide Bedingungen mathematisch gleichwertig. Die erste vermeidet jedoch ein Produkt, das den Wertebereich von int überschreiten und undefiniertes Verhalten auslösen könnte. Im schlimmsten Fall führt der Algorithmus O(√n) Prüfungen durch und benötigt O(1) zusätzlichen Speicher.
Beispiele
#include <stdio.h>
static int is_prime(int n)
{
if (n < 2) return 0;
if (n == 2) return 1;
if (n % 2 == 0) return 0;
for (int d = 3; d <= n / d; d += 2) {
if (n % d == 0) return 0;
}
return 1;
}
int main(void)
{
const int values[] = {-7, 0, 1, 2, 4, 9, 29, 49};
for (size_t i = 0; i < sizeof values / sizeof values[0]; ++i) {
printf("%d: %d\n", values[i], is_prime(values[i]));
}
return 0;
}Ergebnis
-7: 0 0: 0 1: 0 2: 1 4: 0 9: 0 29: 1 49: 0
Der angezeigte Code und das angegebene Ergebnis wurden in einer isolierten Umgebung mit der im Prüfnachweis für genau diese Version dokumentierten Methode verifiziert.