C Program for Prime Numbers in a Range – with Sieve of Eratosthenes

This C program generates and prints all prime numbers in a given range and reports the total count. It uses an efficient is_prime() function with a √n bound, plus a Sieve of Eratosthenes for cases where you need all primes up to a large limit.

Trial Division — Check Each Number in the Range

For moderate ranges, check each number individually with a helper function:

#include <stdio.h>

int is_prime(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 m, n, i, count = 0;

    printf("Enter range start and end: ");
    scanf("%d %d", &m, &n);

    printf("Prime numbers between %d and %d:\n", m, n);
    for (i = m; i <= n; i++) {
        if (is_prime(i)) {
            printf("%d ", i);
            count++;
        }
    }
    printf("\nTotal primes: %d\n", count);
    return 0;
}

How to Compile and Run

gcc -Wall -o primerange primerange.c
./primerange

Sample Output

Enter range start and end: 1 50
Prime numbers between 1 and 50:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
Total primes: 15

Enter range start and end: 100 120
Prime numbers between 100 and 120:
101 103 107 109 113
Total primes: 5

Sieve of Eratosthenes — Fast Generation for Large Ranges

When you need all primes up to a large limit (e.g., 1,000,000), the Sieve is far faster. It marks composites rather than testing each number individually:

Create a boolean array sieve[0..n], initialized to true (all assumed prime).
Starting from 2, mark every multiple of 2 as composite, then every multiple of 3, 5, 7, … up to √n.
The unmarked entries that remain are prime.

#include <stdio.h>
#include <string.h>
#define LIMIT 1000001

int sieve[LIMIT];   /* 0 = prime, 1 = composite */

void build_sieve(void)
{
    int i, j;
    memset(sieve, 0, sizeof sieve);
    sieve[0] = sieve[1] = 1;   /* 0 and 1 are not prime */

    for (i = 2; (long)i * i < LIMIT; i++) {
        if (!sieve[i]) {
            for (j = i * i; j < LIMIT; j += i)
                sieve[j] = 1;
        }
    }
}

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

    printf("Enter range start and end (max %d): ", LIMIT - 1);
    scanf("%d %d", &m, &n);

    printf("Primes between %d and %d:\n", m, n);
    for (i = m; i <= n; i++) {
        if (!sieve[i]) {
            printf("%d ", i);
            count++;
        }
    }
    printf("\nTotal primes: %d\n", count);
    return 0;
}

How the Sieve Works — Example for n = 30

Start:  2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Mark ×2: cross 4,6,8,10,12,14,16,18,20,22,24,26,28,30
Mark ×3: cross 9,15,21,27 (6,12... already crossed)
Mark ×5: cross 25 (others already crossed)
Remaining: 2 3 5 7 11 13 17 19 23 29 ← all primes ≤ 30

The inner loop starts at i * i (not 2 * i) because all smaller multiples of i were already marked by earlier primes.

Time and Space Complexity

Method	Time	Space	Best for
Trial division (per number)	O(√n)	O(1)	Checking individual numbers or small ranges
Trial division (range m–n)	O((n−m) × √n)	O(1)	Moderate ranges
Sieve of Eratosthenes	O(n log log n)	O(n)	All primes up to a large fixed limit

What This Program Teaches

The √n bound: if n has no factor ≤ √n, it is prime — the key insight behind all trial division methods
The Sieve pattern: marking multiples is far cheaper than dividing each number — algorithmic thinking over brute force
Starting the inner sieve loop at i * i: all smaller multiples of i are composites of a smaller prime, already marked
(long)i * i: prevents overflow when i is large enough that i * i would wrap an int

Related Programs

As an Amazon Associate we earn from qualifying purchases.

Recommended Book

Loops, functions, and arrays are all covered in The C Programming Language by Kernighan & Ritchie — the definitive reference for C. Also on Amazon.com.

C Program to Print Prime Numbers in a Given Range – Trial Division and Sieve