Znalostná bázaCentrum skúšok
SKSlovenčina
Vybrať jazyk13

CKTIS / C

Test prvočíselnosti skúšobným delením

Zisti, či je celé číslo prvočíslo, skúšaním možných deliteľov len po jeho druhú odmocninu. Podmienka `d <= n / d` v jazyku C overuje túto hranicu bez rizika pretečenia pri násobení.

Verzia: C23; repository compiler flag, production runtime not attested

Syntax

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

Test prvočíselnosti skúšobným delením overuje, či má n iného deliteľa než 1 a n. Najprv zamietni n < 2, prijmi n == 2 a zamietni všetky ostatné párne čísla. Pri zvyšných kandidátoch skúšaj iba nepárne hodnoty d, počnúc 3. Ak n % d == 0, číslo je zložené. Ak cyklus nenájde žiadneho deliteľa, číslo je prvočíslo.

Delitele sa vyskytujú v dvojiciach: ak n = a * b a oba činitele sú väčšie ako 1, aspoň jeden z nich neprevyšuje druhú odmocninu z n. Hranica sa započítava: pri 49 musí cyklus vyskúšať aj 7.

Na overenie hranice pre delitele bez pretečenia použi d <= n / d namiesto d * d <= n. Pre kladné n a d zaokrúhľuje celočíselné delenie v jazyku C podiel nadol, takže obe podmienky sú matematicky rovnocenné. Prvá sa však vyhne výpočtu súčinu, ktorý by mohol prekročiť rozsah typu int a spôsobiť nedefinované správanie. Algoritmus v najhoršom prípade vykoná O(√n) pokusov a využíva O(1) dodatočnej pamäte.

Príklady

#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;
}

Výsledok

-7: 0
0: 0
1: 0
2: 1
4: 0
9: 0
29: 1
49: 0

Zobrazený kód a uvedený výsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.

Zdroje