Step 7 of 7

Challenge: is it prime?

A prime is a whole number greater than 1 whose only divisors are 1 and itself: 2, 3, 5, 7, 11, 13 and so on. 1 is not prime, and neither are 0 or negative numbers.

The idea

To test n, try dividing it by every candidate d starting at 2. If any d divides it evenly (n % d == 0), it isn't prime, and you can return 0 immediately. If none do, it's prime.

Why stop at the square root?

If n has a divisor bigger than its square root, it must also have one smaller than the square root (because they multiply to n: for 91, 7 x 13, and 7 is below the square root, about 9.5). So once you've tried every d with d * d <= n and found nothing, there's nothing left to find. For a number around a million, that's about 1,000 checks instead of 1,000,000.

Writing the loop condition as d * d <= n avoids needing a square-root function and floating-point numbers. (For n very close to the largest int, about 2.1 billion, d * d itself can overflow; d <= n / d is the fully safe form. The tests here stay well below that.)

Here's the same "try divisors" pattern used for a different job, counting how many divisors a number has:

#include <stdio.h>

int count_divisors(int n) {
    int count = 0;
    for (int d = 1; d <= n; d++) {
        if (n % d == 0) {
            count++;
        }
    }
    return count;
}

int main(void) {
    printf("%d %d %d\n", count_divisors(12), count_divisors(7), count_divisors(1));
    return 0;
}

6 2 1

Handle the edge cases first

Start the function by dealing with the special inputs (anything below 2) and returning right away. Then the loop only has to handle the normal case. Hidden tests will definitely try 0, 1, 2 and a large prime.

Your turn: write int is_prime(int n) that returns 1 for primes and 0 otherwise. Only test divisors up to the square root (d * d <= n) so it stays fast for big numbers.

Previous: Recursion