Prime Number in C: Safe Test, Range Program and Dry Run

A prime number in C is tested by checking whether an integer greater than 1 has any divisor other than 1 and itself. The number 2 is prime; 0 and 1 are not. To test one value, trial division through its square root is enough. Use divisor <= n / divisor, not divisor * divisor <= n, to avoid an overflowing multiplication.

Complete prime-number program

Supply one unsigned decimal integer from 0 through 60000. The deliberately small limit fits even the minimum C17 range of unsigned int and keeps this teaching program bounded. Leading zeros and surrounding whitespace are accepted; signs, negative input, fractions, extra tokens and out-of-range values are rejected. This is not a cryptographic primality test.

#include <stdio.h>
#include <ctype.h>

/* One unsigned decimal token, surrounding whitespace, then EOF. */
static int read_bounded(unsigned int *out, unsigned int limit) {
    int ch;
    unsigned int value = 0;
    do { ch = getchar(); } while (ch != EOF && isspace(ch));
    if (ch < '0' || ch > '9') return 0;
    do {
        unsigned int digit = (unsigned int)(ch - '0');
        if (value > limit / 10 ||
            (value == limit / 10 && digit > limit % 10)) return 0;
        value = value * 10 + digit;
        ch = getchar();
    } while (ch >= '0' && ch <= '9');
    while (ch != EOF && isspace(ch)) ch = getchar();
    if (ch != EOF) return 0;
    *out = value;
    return 1;
}

int is_prime(unsigned int n) {
    if (n < 2) return 0;
    if (n % 2 == 0) return n == 2;
    for (unsigned int divisor = 3; divisor <= n / divisor; divisor += 2) {
        if (n % divisor == 0) return 0;
    }
    return 1;
}

int main(void) {
    unsigned int n;
    if (!read_bounded(&n, 60000)) {
        fputs("Enter one whole number from 0 to 60000.\n", stderr);
        return 1;
    }
    printf("%u: %s\n", n, is_prime(n) ? "prime" : "not prime");
    return 0;
}

29

29: prime

The parser reads the entire batch stdin through EOF. is_prime returns 0 for values below 2, handles the only even prime separately, then tests odd divisors starting at 3. That halves the trial candidates after handling 2 without changing the result.

Why checking up to the square root works

If n = a × b is composite, both a and b cannot exceed √n, because their product would then exceed n. At least one factor is at or below √n. Therefore finding no divisor through that bound proves primality for the integer being tested.

For positive integers, divisor <= n / divisor is equivalent to divisor × divisor <= n. Integer division rounds down, which is compatible with this inclusive integer bound. The divisor starts at 3, so the division never uses zero. The program avoids both floating-point rounding and a potentially overflowing square.

Dry runs: a square and a prime

The bound must use less than or equal, not strictly less: excluding the exact square root misclassifies 49. Stopping at n / 2 is correct for n > 2 but does far more work than necessary.

Print primes in a bounded range

Edit the inclusive endpoints in this no-stdin program. It checks at most 1000 values, all within 0–60000, and prints a specific message if there are no primes. The order check precedes unsigned subtraction; the upper endpoint keeps the loop increment safely below the type's maximum.

#include <stdio.h>

int is_prime(unsigned int n) {
    if (n < 2) return 0;
    if (n % 2 == 0) return n == 2;
    for (unsigned int divisor = 3; divisor <= n / divisor; divisor += 2) {
        if (n % divisor == 0) return 0;
    }
    return 1;
}

int main(void) {
    unsigned int first = 1, last = 30;
    if (first > last || last > 60000 || last - first > 999) {
        fputs("Use an ordered range of at most 1000 values within 0..60000.\n", stderr);
        return 1;
    }
    int found = 0;
    for (unsigned int n = first; n <= last; ++n) {
        if (is_prime(n)) {
            printf("%s%u", found ? " " : "", n);
            found = 1;
        }
    }
    if (!found) printf("No primes");
    putchar('\n');
    return 0;
}

2 3 5 7 11 13 17 19 23 29

Trial division versus a sieve

For a long contiguous range, compare the sieve of Eratosthenes example. A sieve has a different memory trade-off and does not mean repeatedly calling this function. Faster probabilistic and deterministic large-integer tests exist, but their range guarantees and arithmetic deserve a separate implementation.

Edge cases, mistakes and practice

Negative integers are not primes in this elementary positive-prime definition; the input parser rejects them rather than pretending they are unsigned values. Test 2 and 3, the composites 4 and 9, squares 25 and 49, the prime 59999, and the endpoint 60000. A number being odd is necessary for primes above 2, not sufficient: 9, 15 and 21 are odd composites.

Try the range 14–16: print No primes. Try 0–3: print 2 3. For a code-reading exercise, remove the even-number shortcut and test every divisor starting at 2; the answers should agree, but more trial divisions will be performed. Do not remove the n < 2 guard.

Review functions, factorial overflow checks, and loop practice. Run links send the exact displayed code and input to the online compiler; the reference output on this page is not a fresh execution result.

Frequently asked questions

Is 1 a prime number?

No. A prime has exactly two positive divisors; 1 has only one.

Why not call sqrt?

The integer division bound avoids floating-point rounding, multiplication overflow and a math-library linking requirement. It also directly expresses the factor-pair proof.

Can I remove the input limit for security or cryptography?

No. This is a bounded teaching example, not a reviewed cryptographic implementation. Large inputs, big integers and security requirements need different tools and explicit guarantees.