CKTIS / C
Test pierwszości metodą próbnego dzielenia
Sprawdź, czy liczba całkowita jest pierwsza, testując dzielniki tylko do jej pierwiastka kwadratowego. W C warunek `d <= n / d` pozwala wyznaczyć tę granicę bez ryzyka przepełnienia przy mnożeniu.
Wersja: C23; repository compiler flag, production runtime not attested
Składnia
for (int d = 3; d <= n / d; d += 2) { if (n % d == 0) return 0; }Test pierwszości metodą próbnego dzielenia sprawdza, czy n ma dzielnik inny niż 1 i n. Najpierw odrzuć n < 2, zaakceptuj n == 2, a następnie odrzuć pozostałe liczby parzyste. Dla pozostałych kandydatów na liczby pierwsze sprawdzaj tylko nieparzyste d, zaczynając od 3. Jeśli n % d == 0, liczba jest złożona. Jeśli pętla nie znajdzie dzielnika, liczba jest pierwsza.
Dzielniki występują parami: jeśli n = a * b i oba czynniki są większe od 1, przynajmniej jeden z nich nie przekracza pierwiastka kwadratowego z n. Granica jest włącznie: dla 49 trzeba jeszcze sprawdzić 7.
Aby sprawdzić granicę bez przepełnienia, użyj d <= n / d zamiast d * d <= n. Dla dodatnich n i d dzielenie całkowite w C zaokrągla iloraz w dół, więc oba warunki są matematycznie równoważne. Pierwszy nie oblicza jednak iloczynu, który mógłby przekroczyć zakres typu int i spowodować niezdefiniowane zachowanie. Algorytm wykonuje w najgorszym przypadku O(√n) prób i zużywa O(1) dodatkowej pamięci.
Przykłady
#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;
}Wynik
-7: 0 0: 0 1: 0 2: 1 4: 0 9: 0 29: 1 49: 0
Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.