Znalostní bázeCentrum zkoušek
CSČeština
Vybrat jazyk13

CKTIS / C

Test prvočíselnosti zkušebním dělením

Zjistěte, zda je celé číslo prvočíslem, zkoušením možných dělitelů jen do jeho druhé odmocniny. Podmínka `d <= n / d` v jazyce C ověřuje tuto mez bez rizika přetečení při násobení.

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

Syntaxe

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

Test prvočíselnosti zkušebním dělením ověřuje, zda má n jiného dělitele než 1 a n. Nejprve zamítněte n < 2, přijměte n == 2 a zamítněte všechna ostatní sudá čísla. U zbývajících kandidátů zkoušejte jen lichá d počínaje 3. Pokud n % d == 0, je číslo složené. Jestliže cyklus žádného dělitele nenajde, je číslo prvočíslem.

Dělitelé tvoří dvojice: pokud n = a * b a oba činitelé jsou větší než 1, alespoň jeden z nich nepřevyšuje druhou odmocninu z n. Mez se počítá: pro 49 musí cyklus vyzkoušet i 7.

Chcete-li ověřit mez pro dělitele bez přetečení, použijte d <= n / d místo d * d <= n. Pro kladná n a d zaokrouhluje celočíselné dělení v jazyce C podíl dolů, takže jsou obě podmínky matematicky rovnocenné. První se však vyhne výpočtu součinu, který by mohl překročit rozsah typu int a způsobit nedefinované chování. Algoritmus v nejhorším případě provede O(√n) pokusů a využije O(1) dodatečné paměti.

Pří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ýsledek

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

Zobrazený kód a uvedený výsledek byly ověřeny v izolovaném prostředí metodou zaznamenanou v dokladu o ověření této přesné verze.

Zdroje