CKTIS / C
Priemtest door proefdeling
Controleer of een geheel getal priem is door mogelijke delers alleen tot aan de vierkantswortel te testen. In C controleert `d <= n / d` die grens zonder het risico op overflow bij vermenigvuldiging.
Versie: C23; repository compiler flag, production runtime not attested
Syntax
for (int d = 3; d <= n / d; d += 2) { if (n % d == 0) return 0; }De priemtest door proefdeling controleert of n naast 1 en n nog een deler heeft. Wijs eerst n < 2 af, accepteer n == 2 en wijs alle andere even getallen af. Test voor de overgebleven kandidaten alleen oneven waarden van d, beginnend bij 3. Als n % d == 0, is het getal samengesteld. Vindt de lus geen deler, dan is het getal priem.
Delers komen in paren voor: als n = a * b en beide factoren groter zijn dan 1, is minstens één ervan niet groter dan de vierkantswortel van n. De grens telt mee: bij 49 moet de lus ook 7 testen.
Gebruik d <= n / d in plaats van d * d <= n om de delergrens zonder overflow te controleren. Voor positieve n en d rondt gehele deling in C het quotiënt naar beneden af, dus de twee voorwaarden zijn wiskundig gelijkwaardig. De eerste vermijdt echter een product dat buiten het bereik van int zou kunnen vallen en ongedefinieerd gedrag zou kunnen veroorzaken. In het slechtste geval voert het algoritme O(√n) tests uit en gebruikt het O(1) extra geheugen.
Voorbeelden
#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;
}Resultaat
-7: 0 0: 0 1: 0 2: 1 4: 0 9: 0 29: 1 49: 0
De getoonde code en het opgegeven resultaat zijn in een geïsoleerde omgeving geverifieerd met de methode die in het verificatiebewijs voor exact deze versie is vastgelegd.