CKTIS / C
Provjera prostih brojeva probnim dijeljenjem
Provjeri je li cijeli broj prost tako da ispitaš moguće djelitelje samo do njegova kvadratnog korijena. U jeziku C uvjet `d <= n / d` provjerava tu granicu bez rizika od prekoračenja raspona pri množenju.
Verzija: C23; repository compiler flag, production runtime not attested
Sintaksa
for (int d = 3; d <= n / d; d += 2) { if (n % d == 0) return 0; }Provjerom prostih brojeva probnim dijeljenjem utvrđuješ ima li n djelitelj osim 1 i n. Najprije odbaci n < 2, prihvati n == 2 i odbaci sve ostale parne brojeve. Za preostale kandidate ispituj samo neparne vrijednosti d, počevši od 3. Ako vrijedi n % d == 0, broj je složen. Ako petlja ne pronađe nijedan djelitelj, broj je prost.
Djelitelji dolaze u parovima: ako vrijedi n = a * b i oba su faktora veća od 1, barem jedan od njih nije veći od kvadratnog korijena broja n. Granica je uključena: za 49 petlja mora ispitati i 7.
Za provjeru granice djelitelja bez prekoračenja raspona upotrijebi d <= n / d umjesto d * d <= n. Za pozitivne n i d cjelobrojno dijeljenje u jeziku C zaokružuje kvocijent prema dolje, pa su ta dva uvjeta matematički ekvivalentna. Prvi ipak izbjegava računanje umnoška koji bi mogao prekoračiti raspon tipa int i uzrokovati nedefinirano ponašanje. U najgorem slučaju algoritam izvodi O(√n) provjera i koristi O(1) dodatne memorije.
Primjeri
#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;
}Rezultat
-7: 0 0: 0 1: 0 2: 1 4: 0 9: 0 29: 1 49: 0
Prikazani kôd i navedeni rezultat provjereni su u izoliranom okruženju metodom zabilježenom u dokazu provjere za ovu točnu verziju.