Knowledge baseExam Center
ENEnglish
Choose language13

CKTIS / C

Primality testing by trial division

Check whether an integer is prime by testing divisors only up to its square root. In C, the condition `d <= n / d` checks that bound without risking overflow from multiplication.

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

Syntax

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

The trial division primality test checks whether n has a divisor other than 1 and n. First reject n < 2, accept n == 2, and reject all other even numbers. For the remaining candidates, test only odd d starting at 3. If n % d == 0, the number is composite. If the loop finds no divisor, the number is prime.

Divisors come in pairs: if n = a * b and both factors are greater than 1, at least one is no larger than the square root of n. The bound is inclusive: for 49, the loop still needs to test 7.

To check the divisor bound without overflow, use d <= n / d instead of d * d <= n. For positive n and d, C integer division rounds the quotient down, so the two conditions are mathematically equivalent. The first avoids computing a product that could exceed the range of int and cause undefined behavior. The algorithm makes O(√n) trials in the worst case and uses O(1) extra space.

Examples

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

Result

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

The displayed code and declared result were verified in an isolated environment using the method recorded in the verification evidence for this exact version.

Sources