Prime Numbers in C Programming – Complete Guide

What is a Prime Number?

A prime number is a natural number greater than 1 that has only two factors: 1 and itself.

Examples → 2, 3, 5, 7, 11, 13 …
Not Prime (Composite) → 4 (factors: 1,2,4), 6 (factors: 1,2,3,6)

Logic to Check Prime Number in C

Take a number n as input.
If n <= 1, it’s not prime.
Check divisibility from 2 to n/2 (or √n for efficiency).
If divisible, then it’s not prime.
Otherwise, it’s prime.

#include <stdio.h>

int main() {
    int n, i, flag = 0;
    printf("Enter a number: ");
    scanf("%d", &n);

    if (n <= 1) {
        printf("%d is not a prime number.\n", n);
        return 0;
    }

    for (i = 2; i <= n/2; i++) {
        if (n % i == 0) {
            flag = 1;  // Not prime
            break;
        }
    }

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

    return 0;
}

Example Run

Optimized Code (Check till √n only)

#include <stdio.h>
#include <math.h>

int main() {
    int n, i, flag = 0;
    printf("Enter a number: ");
    scanf("%d", &n);

    if (n <= 1) {
        printf("%d is not a prime number.\n", n);
        return 0;
    }

    for (i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            flag = 1;
            break;
        }
    }

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

    return 0;
}

Checking up to √n reduces execution time for large numbers.

Program to Print Prime Numbers in a Range

#include <stdio.h>

int main() {
    int start, end, i, j, flag;

    printf("Enter start and end values: ");
    scanf("%d %d", &start, &end);

    printf("Prime numbers between %d and %d are: ", start, end);

    for (i = start; i <= end; i++) {
        if (i <= 1)
            continue;

        flag = 0;
        for (j = 2; j <= i/2; j++) {
            if (i % j == 0) {
                flag = 1;
                break;
            }
        }
        if (flag == 0)
            printf("%d ", i);
    }
    return 0;
}