Prime Number Program in C – Basic and Optimized

A prime number program in C checks whether a given integer is prime — divisible only by 1 and itself. Numbers like 2, 3, 5, 7, 11, and 13 are prime; 4, 6, 9, and 12 are not.

This page covers two approaches: a basic trial division and an optimized version that skips even numbers, reducing the checks by half. It also shows how to print all primes up to a limit.

What Makes a Number Prime?

A number n > 1 is prime if no integer from 2 to √n divides it evenly. We only need to check up to √n because if n has a factor larger than √n, it must also have a corresponding factor smaller than √n — so we would have already found it.

Prime Number Program in C — Basic Version

#include <stdio.h>

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

int main(void)
{
    int n;
    printf("Enter a number: ");
    scanf("%d", &n);

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

    return 0;
}

How to Compile and Run

gcc -Wall -o prime prime.c
./prime

Sample Output

Enter a number: 17
17 is a prime number.

Enter a number: 15
15 is not a prime number.

Enter a number: 2
2 is a prime number.

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

Optimized Version — Skip Even Numbers

After checking 2 separately, only odd numbers can be prime. Checking only odd divisors halves the number of iterations:

#include <stdio.h>

int isPrime(int n)
{
    int i;
    if (n < 2)  return 0;
    if (n == 2) return 1;
    if (n % 2 == 0) return 0;     /* even numbers > 2 are not prime */

    for (i = 3; (long)i * i <= n; i += 2)  /* check odd divisors only */
        if (n % i == 0)
            return 0;
    return 1;
}

int main(void)
{
    int n;
    printf("Enter a number: ");
    scanf("%d", &n);

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

    return 0;
}

The loop starts at 3 and increments by 2, so it tests 3, 5, 7, 9, 11, … — only odd numbers. Combined with the early exit for even inputs, this roughly halves the work compared to the basic version.

Print All Primes Up to N

Using the same isPrime() function to print all primes from 2 to a given limit:

#include <stdio.h>

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

int main(void)
{
    int n, i, count = 0;
    printf("Print primes up to: ");
    scanf("%d", &n);

    for (i = 2; i <= n; i++) {
        if (isPrime(i)) {
            printf("%d ", i);
            count++;
        }
    }
    printf("\nTotal primes: %d\n", count);
    return 0;
}

Print primes up to: 30
2 3 5 7 11 13 17 19 23 29
Total primes: 10

Time Complexity

Version	Time (per number)	Notes
Basic trial division	O(√n)	Tests all integers 2 to √n
Optimized (skip evens)	O(√n / 2)	Tests only odd integers
Sieve of Eratosthenes	O(n log log n)	Best for generating all primes up to n — see prime numbers in a range

What This Program Teaches

Why you only need to check divisors up to √n — a key number-theory insight that appears in many interview problems
The (long)i * i <= n form: casting to long before multiplying prevents integer overflow when i is near the square root of INT_MAX
Why 1 is not prime: by convention, 1 is excluded so that prime factorizations are unique
The even-number optimization: handling 2 as a special case lets the main loop step by 2, eliminating half the work

Related Programs

As an Amazon Associate we earn from qualifying purchases.

Recommended Book

Number-theoretic programs and loops like these are natural practice exercises after reading chapters 1–3 of The C Programming Language by Kernighan & Ritchie. Also on Amazon.com.

Prime Number Program in C – Check if a Number is Prime