База знанияИзпитен център
BGБългарски
Избери език13

CKTIS / C

Проверка за просто число чрез пробно деление

Провери дали едно цяло число е просто, като изпробваш възможните делители само до квадратния му корен. В C условието `d <= n / d` проверява тази граница без риск от препълване при умножение.

Версия: C23; repository compiler flag, production runtime not attested

Синтаксис

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

Проверката чрез пробно деление установява дали n има делител, различен от 1 и n. Първо отхвърли n < 2, приеми n == 2 и отхвърли всички останали четни числа. За останалите кандидати проверявай само нечетни стойности на d, като започнеш от 3. Ако n % d == 0, числото е съставно. Ако цикълът не намери делител, числото е просто.

Делителите се срещат по двойки: ако n = a * b и двата множителя са по-големи от 1, поне единият от тях не надвишава квадратния корен на n. Границата е включена: при 49 цикълът трябва да провери и 7.

За да провериш границата за делителите без препълване, използвай d <= n / d вместо d * d <= n. При положителни n и d целочисленото деление в C закръгля частното надолу, затова двете условия са математически равностойни. Първото обаче избягва изчисляването на произведение, което би могло да надхвърли обхвата на типа int и да доведе до неопределено поведение. В най-лошия случай алгоритъмът прави O(√n) проверки и използва O(1) допълнителна памет.

Примери

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

Резултат

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

Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.

Източници