Prime Number Program in C: Code, Logic and Optimisation

A prime number program in C checks whether an integer greater than 1 has any divisor other than 1 and itself. The standard method is a loop from 2 up to the square root of n testing n % i == 0; if no remainder is ever zero, n is prime. The square root bound is not a shortcut or an approximation, it is provably enough, and it turns roughly a million divisions into roughly a thousand for a number near one million.

This page gives five complete, compilable C programs, from the simplest version to the Sieve of Eratosthenes, and explains the logic of each. Every program handles the edge cases correctly, which is where most student submissions lose marks.

Prime number program in C (complete working code)

Start with the direct version. It tests every integer from 2 up to n-1 as a possible divisor.

#include <stdio.h>

int main(void)
{
    int n, i;
    int isPrime = 1;

    printf("Enter a positive integer: ");
    if (scanf("%d", &n) != 1) {
        printf("Invalid input.\n");
        return 1;
    }

    if (n <= 1) {
        isPrime = 0;
    } else {
        for (i = 2; i <= n - 1; i++) {
            if (n % i == 0) {
                isPrime = 0;
                break;
            }
        }
    }

    if (isPrime == 1)
        printf("%d is a prime number.\n", n);
    else
        printf("%d is not a prime number.\n", n);

    return 0;
}

Compile and run it with:

gcc prime.c -o prime
./prime

Sample output:

Enter a positive integer: 29
29 is a prime number.

Enter a positive integer: 1
1 is not a prime number.

The logic, line by line

• #include <stdio.h> brings in printf and scanf. In C these are functions from the standard input-output header, not stream objects.
• int isPrime = 1; is a flag. C89 has no bool type, so an int holding 1 for true and 0 for false is the normal idiom. In C99 and later you may include <stdbool.h> and use bool.
• scanf("%d", &n) reads an integer. The & is required; scanf needs the address of the variable. Comparing the return value with 1 confirms one item was actually read, so typing letters does not leave n holding garbage.
• if (n <= 1) rejects 1, 0 and every negative number before the loop runs. This single line is the difference between a correct program and the one most blogs publish.
• for (i = 2; i <= n - 1; i++) tries each candidate divisor. For n = 2 the condition 2 <= 1 is false straight away, the loop body never executes, the flag stays 1, and the program correctly reports 2 as prime.
• if (n % i == 0) is the actual test. The modulus operator gives the remainder; a zero remainder means i divides n exactly, so n is composite.
• break; leaves the loop the moment a divisor is found. Without it the answer is still right, but the program keeps dividing for no reason.

The edge cases: 1, 2, 0 and negative numbers

A prime number is a natural number greater than 1 whose only positive divisors are 1 and itself. Read that definition strictly and the awkward cases answer themselves.

Two failures show up again and again in submitted code. A program that loops for (i = 2; i < n; i++) with no guard will call 1 prime, because the loop never runs. A program that special-cases even numbers before checking for 2 will call 2 composite. Test your code on 1 and on 2 before you test it on anything else.

Optimised version: why you only need to check up to the square root

Here is the proof, and it is short. Suppose n is composite, so n = a × b where both a and b are integers greater than 1. If both a and b were larger than the square root of n, then a × b would be larger than n, which contradicts a × b = n. So at least one of the two factors must be less than or equal to the square root of n.

Every composite number therefore has a divisor no larger than its square root. If you search up to the square root and find nothing, the number is prime. Take 36: its factor pairs are 1×36, 2×18, 3×12, 4×9 and 6×6. The smaller member of every pair is at most 6, which is the square root of 36. The pairs after that are just the earlier ones reversed.

#include <stdio.h>

int isPrime(int n)
{
    int i;

    if (n <= 1)
        return 0;

    for (i = 2; i * i <= n; i++) {
        if (n % i == 0)
            return 0;
    }

    return 1;
}

int main(void)
{
    int n;

    printf("Enter a positive integer: ");
    if (scanf("%d", &n) != 1) {
        printf("Invalid input.\n");
        return 1;
    }

    if (isPrime(n) == 1)
        printf("%d is a prime number.\n", n);
    else
        printf("%d is not a prime number.\n", n);

    return 0;
}

Notice the loop condition: i * i <= n, not i <= sqrt(n). Using i * i keeps everything in integer arithmetic. Calling sqrt() needs <math.h>, returns a double, links with -lm on many systems, and can round a perfect square such as 49 down to 6.999999, which would make the program call 49 prime. Integer multiplication has no such trap.

One caution for very large inputs: i * i can overflow int if n is close to the maximum value of the type. If that matters, write the condition as i <= n / i instead, which compares the same two quantities without ever forming the product.

Further optimisation: skip even numbers, then use 6k ± 1

After 2, no even number is prime, so half the candidate divisors are wasted work. Handle 2 on its own, reject the other even numbers, then step through odd divisors only:

int isPrime(int n)
{
    int i;

    if (n <= 1)
        return 0;
    if (n == 2)
        return 1;
    if (n % 2 == 0)
        return 0;

    for (i = 3; i * i <= n; i += 2) {
        if (n % i == 0)
            return 0;
    }

    return 1;
}

You can go one step further. Every integer can be written as 6k, 6k+1, 6k+2, 6k+3, 6k+4 or 6k+5. The forms 6k, 6k+2 and 6k+4 are divisible by 2, and 6k+3 is divisible by 3. So apart from 2 and 3 themselves, every prime is of the form 6k − 1 or 6k + 1. Test 2 and 3 first, then check only that pair in each block of six:

#include <stdio.h>

int isPrime(long n)
{
    long i;

    if (n <= 1)
        return 0;
    if (n <= 3)
        return 1;                    /* 2 and 3 are prime */
    if (n % 2 == 0 || n % 3 == 0)
        return 0;

    for (i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0)
            return 0;
    }

    return 1;
}

int main(void)
{
    long n;

    printf("Enter a positive integer: ");
    if (scanf("%ld", &n) != 1) {
        printf("Invalid input.\n");
        return 1;
    }

    if (isPrime(n) == 1)
        printf("%ld is a prime number.\n", n);
    else
        printf("%ld is not a prime number.\n", n);

    return 0;
}

Trace it on 121 to see it work. 121 is not below 4, it is not divisible by 2 or 3, so the loop starts at i = 5. Since 25 is at most 121, it tests 121 % 5 = 1 and 121 % 7 = 2, both non-zero. Next i = 11, and 121 is at most 121, so it tests 121 % 11 = 0 and returns 0. Correct, because 121 = 11 × 11. This version does about a third of the divisions of the plain square root loop.

C program to print all prime numbers in a range

Wrap the test in an outer loop over the range. Keeping the test in its own function is what makes this easy.

#include <stdio.h>

int isPrime(int n)
{
    int i;

    if (n <= 1)
        return 0;
    if (n == 2)
        return 1;
    if (n % 2 == 0)
        return 0;

    for (i = 3; i * i <= n; i += 2) {
        if (n % i == 0)
            return 0;
    }

    return 1;
}

int main(void)
{
    int low, high, num, count = 0;

    printf("Enter the lower and upper limits: ");
    if (scanf("%d %d", &low, &high) != 2) {
        printf("Invalid input.\n");
        return 1;
    }

    if (low > high) {          /* accept the limits in either order */
        int temp = low;
        low = high;
        high = temp;
    }

    printf("Prime numbers between %d and %d:\n", low, high);

    for (num = low; num <= high; num++) {
        if (isPrime(num) == 1) {
            printf("%d ", num);
            count++;
        }
    }

    printf("\nTotal: %d prime numbers.\n", count);

    return 0;
}

Sample run:

Enter the lower and upper limits: 1 50
Prime numbers between 1 and 50:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
Total: 15 prime numbers.

There are 15 primes below 50, and 25 below 100, so those two counts are a quick way to check your program is right.

Sieve of Eratosthenes in C

Testing each number one at a time repeats a lot of work. If you want every prime up to some limit, mark multiples instead of dividing. The algorithm is over two thousand years old and still the fastest simple method for this job.

Take an array of flags, one per number. Start at 2. Every multiple of 2 above 2 itself is composite, so mark 4, 6, 8 and so on. Move to the next unmarked number, 3, and mark 9, 12, 15 and so on. Keep going. Whatever is still unmarked at the end is prime.

#include <stdio.h>

#define MAX 1000000

char composite[MAX + 1];   /* global, so every element starts as 0 */

int main(void)
{
    int n, i, j, count = 0;

    printf("Print all primes up to n: ");
    if (scanf("%d", &n) != 1 || n < 2 || n > MAX) {
        printf("Enter a value between 2 and %d.\n", MAX);
        return 1;
    }

    for (i = 2; i * i <= n; i++) {
        if (composite[i] == 0) {
            for (j = i * i; j <= n; j += i)
                composite[j] = 1;
        }
    }

    for (i = 2; i <= n; i++) {
        if (composite[i] == 0) {
            printf("%d ", i);
            count++;
        }
    }

    printf("\nCount: %d\n", count);

    return 0;
}

Two details do the heavy lifting. The outer loop stops at the square root of n, for the same reason as before: any composite below n has already been marked by a factor no larger than the square root. The inner loop starts at i * i, not at 2 * i, because every smaller multiple of i carries a smaller prime factor and was already marked. Declaring the array at file scope matters too, since a global array of this size is zero-initialised automatically and would not fit comfortably on the stack.

Print all primes up to n: 100
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

Time complexity comparison

Read the last row carefully, because it is a different question. The square root test answers “is this one number prime”. The sieve answers “which numbers up to n are prime”. If you need many primes, the sieve wins by a wide margin; if you need one check on one number, use the square root version. The sieve also uses O(n) memory, while trial division uses none.

Common mistakes in prime number programs

• Calling 1 prime. A bare loop from 2 to n-1 never executes for n = 1, so the flag stays true. Always guard with if (n <= 1).
• Calling 2 composite. Happens when even numbers are rejected before 2 is checked. Handle n == 2 first.
• Using sqrt() in the loop condition. Floating-point rounding can cut a perfect square short. Use i * i <= n.
• Resetting the flag inside the loop. If isPrime = 1; sits inside the loop body, one later non-divisor wipes out the evidence of an earlier divisor.
• Writing = instead of ==. if (n % i = 0) is not a comparison and will not compile as intended.
• Forgetting the & in scanf. scanf("%d", n) passes a value where an address is needed, and the program usually crashes.
• Printing inside the loop without a break. A composite number with several divisors then prints “not prime” more than once.

C vs C++: what changes for this program

The slug and the queries here are for C, and the code above is C. If you are asked for the C++ version in the same lab, only the input and output change; the primality logic is identical.

Do not mix them. Writing cout in a .c file compiled with gcc gives an undeclared identifier error, and that is the most frequent compile failure students hit when they copy code from a page that quietly switched languages halfway through.

References

• Algorithm and Sieve of Eratosthenes background, Wikipedia.
• GeeksforGeeks – Computer Science, for further practice problems on primality testing.

FAQs

What is the prime number program in C?

It is a program that reads an integer n and reports whether it is prime. It rejects any n of 1 or less, then loops candidate divisors i from 2 while i * i <= n, testing n % i == 0. A zero remainder means n is composite; if the loop finishes with no divisor found, n is prime.

Why check divisors only up to the square root of n?

If n is composite it can be written as a × b with both factors above 1. Both factors cannot be larger than the square root of n, because their product would then exceed n. So every composite number has a divisor at or below its square root, and finding none there proves the number is prime.

Is 1 a prime number in C programs?

No. 1 has only one positive divisor, while a prime must have exactly two distinct divisors, 1 and itself. Many programs get this wrong because a loop from 2 to n-1 never runs for n = 1. Add an explicit if (n <= 1) return 0; check.

Is 2 a prime number?

Yes. 2 is divisible only by 1 and 2, and it is the smallest prime as well as the only even prime. Every other even number has 2 as a divisor, which is why optimised programs test 2 separately and then check odd divisors only.

Which is faster, trial division or the Sieve of Eratosthenes?

For a single number, trial division up to the square root is faster and needs no extra memory, at O(√n). For every prime up to a limit n, the sieve is far faster at O(n log log n), but it needs an array of n flags. Pick the one that matches the question being asked.

Related Topics on EngineeringHulk

• 👉 C Operators
• 👉 C Programming
• 👉 OOP Concepts in C++ — Classes, Inheritance & Polymorphism
• 👉 Greater than sign (>) with examples
• 👉 Number Theory, Groups & Algebraic Structures
• 👉 C Programming Basics — Data Types, Operators & Control Flow