Prime number program in C: from simple loop to the Sieve of Eratosthenes

"Write a program that checks whether a number is prime" is one of the first exercises in every C course, and it is a good one: the simplest answer works, and each improvement teaches something about how to think about speed. A prime number is a whole number greater than 1 whose only divisors are 1 and itself: 2, 3, 5, 7, 11. Numbers with more divisors are composite (4, 6, 9), and 0 and 1 are neither. This post builds four versions, from the one a beginner writes to the one used in practice. Each program was compiled with clang -O2 -Wall -Wextra -std=c11 and run; the timings come from a laptop and only the ratios matter.

Method 1: try every divisor up to n/2

The idea comes straight from the definition: if any number from 2 up to somewhere below n divides n, it is not prime. A divisor larger than n/2 is impossible (apart from n itself), so we can stop at n / 2.

#include <stdio.h>

int main(void) {
    int number;
    printf("Enter a number: ");
    if (scanf("%d", &number) != 1) return 1;

    if (number <= 1) {
        printf("%d is not prime\n", number);
        return 0;
    }
    int is_prime = 1;
    for (int d = 2; d <= number / 2; d++) {
        if (number % d == 0) { is_prime = 0; break; }
    }
    printf("%d is %s\n", number, is_prime ? "prime" : "not prime");
    return 0;
}

Running it with 97, 100 and 1 gave 97 is prime, 100 is not prime and 1 is not prime. Details worth understanding:

• Numbers below 2 are handled first. Without that check, 0 and 1 would wrongly come out as prime, because the loop never runs.
• A flag (is_prime) records the result, and break stops as soon as a divisor is found. 100 is rejected at d = 2, after one test.
• scanf is checked, so letters typed instead of a number do not leave number uninitialised.

The weakness: for a prime near a billion, the loop runs about half a billion times.

Method 2: stop at the square root

If n = a × b and both factors were larger than √n, their product would exceed n. So at least one factor is at most √n, and we only have to test divisors up to √n. For n = 100, that is 10 instead of 50; for a number near a billion it is about 31,623 instead of 500 million.

Avoid calling sqrt() in the loop condition. The test d * d <= n uses integers only, with no floating-point rounding questions. Use long long so that d * d cannot overflow for large n.

Method 3: skip the multiples of 2 and 3

Every prime above 3 has the form 6k − 1 or 6k + 1: after removing all even numbers and all multiples of 3, only those two forms remain (5, 7, 11, 13, 17, 19...). So test 2 and 3 first, then try divisors 5, 7, 11, 13, ..., stepping by 6 and testing both d and d + 2:

#include <stdio.h>
#include <stdbool.h>

bool is_prime(long long n) {
    if (n < 2) return false;
    if (n < 4) return true;                 /* 2 and 3 */
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (long long d = 5; d * d <= n; d += 6) {
        if (n % d == 0 || n % (d + 2) == 0) return false;
    }
    return true;
}

int main(void) {
    long long tests[] = {0, 1, 2, 3, 4, 17, 25, 97, 100, 7919, 1000000007LL, 1000000011LL};
    for (size_t i = 0; i < sizeof tests / sizeof tests[0]; i++)
        printf("%lld -> %s\n", tests[i], is_prime(tests[i]) ? "prime" : "not prime");
    return 0;
}

0 -> not prime
1 -> not prime
2 -> prime
3 -> prime
4 -> not prime
17 -> prime
25 -> not prime
97 -> prime
100 -> not prime
7919 -> prime
1000000007 -> prime
1000000011 -> not prime

The test list includes the awkward cases: 0, 1, 2, 3, a square of a prime (25), and large inputs. 1000000007 is a well-known prime; 1000000011 is divisible by 3. Putting the test in a function that returns a bool makes it reusable and easy to test, which is much better than doing everything in main. This version tests about a third as many divisors as plain square-root trial division.

How much faster is that?

I timed methods 1 and 3 on the prime 1000000007:

n/2 loop: prime in 0.328s | sqrt loop: prime in 0.000008s

That is roughly 40,000 times faster for one number, and the gap grows with n. This is the central lesson of the exercise: a better idea beats a faster computer.

Method 4: all primes up to N with the Sieve of Eratosthenes

Testing numbers one at a time is wasteful when you want every prime up to some limit. The Sieve of Eratosthenes, over two thousand years old, works the other way round: start with a table of all numbers marked "maybe prime", then for each prime found, cross out its multiples.

1. List 2 to N.
2. Take the next number not crossed out (2). It is prime. Cross out 4, 6, 8, ...
3. Take the next uncrossed number (3). It is prime. Cross out 9, 12, 15, ... (start at p × p; smaller multiples are already crossed out).
4. Stop when p × p > N. Everything still uncrossed is prime.

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    int limit = 100;
    char *composite = calloc(limit + 1, 1);
    if (!composite) return 1;
    for (long long i = 2; i * i <= limit; i++) {
        if (!composite[i]) {
            for (long long j = i * i; j <= limit; j += i) composite[j] = 1;
        }
    }
    int count = 0;
    for (int i = 2; i <= limit; i++) {
        if (!composite[i]) { printf("%d ", i); count++; }
    }
    printf("\ncount = %d\n", count);
    free(composite);
    return 0;
}

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 
count = 25

There are 25 primes below 100, which matches the known value. calloc allocates the table already filled with zeros (meaning "not yet crossed out") and free returns it (see dynamic memory in C). Starting the inner loop at i * i and stepping by i is what makes the sieve so efficient: its running time grows only slightly faster than N itself. How fast? For a limit of 100 million:

primes up to 100000000: 5761455 in 0.47s

That is the correct count of primes below 10⁸ (5,761,455), computed in under half a second, using 100 MB of memory for the table. Checking each of those 100 million numbers separately with method 3 would take far longer. The trade-off is memory: if you need only to test a few big numbers, use method 3; if you need all primes up to N, use the sieve. You can halve the memory by storing only odd numbers, or use one bit per number.

Summary

Method	Divisors tried for n ≈ 10⁹	Best for
1. up to n/2	about 500,000,000	learning the definition
2. up to √n	about 31,600	a simple, fast check
3. √n with 6k ± 1	about 10,500	checking single numbers
4. sieve	(all numbers at once)	listing all primes up to N

For numbers with hundreds of digits (cryptography), trial division is hopeless, and programs use probabilistic tests such as Miller-Rabin; that is beyond this exercise, but the same idea of not doing more work than necessary runs through it.

Common mistakes

• Treating 1 (or 0 or negative numbers) as prime.
• Looping up to n instead of n/2 or √n: correct but needlessly slow.
• Using sqrt() with floating-point comparisons and getting off-by-one results; compare d * d <= n with integers.
• Overflow: d * d for int overflows when n is near 2³¹; use long long.
• Forgetting break, so the loop continues after a divisor was found.
• In the sieve, allocating limit instead of limit + 1 bytes and writing past the end of the array.
• Printing "prime" inside the loop for every non-divisor, which prints the answer many times.

Practice

Extend method 3 to print all primes between two numbers typed by the user. Write a function that returns the n-th prime. Print the twin primes below 1,000 (pairs like 11 and 13). Count how many primes there are below 1,000, 10,000 and 100,000, and compare with the approximation n / ln(n). Then port the sieve to the C++ vector version.

Next steps

If any of the syntax above was unfamiliar, work through the C language guide, and read about the way computers run programs in fundamentals of technology. The same problem in Python is a good exercise in the flow control post, which uses loop else to find primes.