Baza znanjaIzpitno središče
SLSlovenščina
Izberi jezik13

CKTIS / C

Preverjanje praštevil s poskusnim deljenjem

Preveri, ali je celo število praštevilo, tako da preizkusiš možne delitelje le do njegovega kvadratnega korena. V C pogoj `d <= n / d` preveri to mejo brez nevarnosti prekoračitve obsega pri množenju.

Različica: C23; repository compiler flag, production runtime not attested

Sintaksa

for (int d = 3; d <= n / d; d += 2) { if (n % d == 0) return 0; }

S poskusnim deljenjem preveriš, ali ima n poleg 1 in n še kakšen delitelj. Najprej zavrni n < 2, sprejmi n == 2 in zavrni vsa druga soda števila. Pri preostalih kandidatih preizkusi samo lihe vrednosti d, začenši s 3. Če velja n % d == 0, je število sestavljeno. Če zanka ne najde nobenega delitelja, je število praštevilo.

Delitelji nastopajo v parih: če velja n = a * b in sta oba faktorja večja od 1, vsaj eden od njiju ni večji od kvadratnega korena števila n. Meja je vključena: pri 49 mora zanka preizkusiti tudi 7.

Da preveriš mejo za delitelje brez prekoračitve obsega, uporabi d <= n / d namesto d * d <= n. Pri pozitivnih n in d celoštevilsko deljenje v C zaokroži količnik navzdol, zato sta pogoja matematično enakovredna. Prvi se izogne izračunu zmnožka, ki bi lahko presegel obseg tipa int in povzročil nedefinirano obnašanje. V najslabšem primeru algoritem opravi O(√n) preizkusov in porabi O(1) dodatnega pomnilnika.

Primeri

#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

Prikazana koda in navedeni rezultat sta bila preverjena v izoliranem okolju z metodo, zapisano v dokazilu o preverjanju te natančne različice.

Viri