Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

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.

Izvori