C Program to Print Prime Numbers in Range

Use a C program with nested loops where the outer loop runs through the range and the inner loop checks if each number is prime by testing divisibility using % operator; print numbers that are prime.

Examples

Inputstart = 1, end = 10

Output2 3 5 7

Inputstart = 10, end = 20

Output11 13 17 19

Inputstart = 22, end = 29

Output23 29

How to Think About It

To find prime numbers in a range, check each number one by one. For each number, test if it is divisible by any number from 2 up to its square root. If it is not divisible by any, it is prime. Print all such numbers.

Algorithm

1

Get the start and end values of the range.

2

For each number from start to end, do the following:

3

Check if the number is less than 2; if yes, skip it.

4

Check divisibility of the number by all integers from 2 to its square root.

5

If the number is not divisible by any, print it as prime.

Code

c

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

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

int main() {
    int start = 1, end = 20;
    for (int num = start; num <= end; num++) {
        if (isPrime(num)) {
            printf("%d ", num);
        }
    }
    return 0;
}

Output

2 3 5 7 11 13 17 19 

Dry Run

Let's trace the program for the range 1 to 10.

1

Check number 1

1 is less than 2, so not prime, skip.

2

Check number 2

2 is >= 2, check divisibility from 2 to sqrt(2)=1 (no checks), so prime, print 2.

3

Check number 3

Check divisibility by 2; 3 % 2 != 0, so prime, print 3.

4

Check number 4

4 % 2 == 0, not prime, skip.

5

Check number 5

Check divisibility by 2; 5 % 2 != 0, prime, print 5.

6

Check number 6

6 % 2 == 0, not prime, skip.

7

Check number 7

Check divisibility by 2 and 3; no divisors, prime, print 7.

8

Check number 8

8 % 2 == 0, not prime, skip.

9

Check number 9

9 % 3 == 0, not prime, skip.

10

Check number 10

10 % 2 == 0, not prime, skip.

Number	Is Prime?
1	No
2	Yes
3	Yes
4	No
5	Yes
6	No
7	Yes
8	No
9	No
10	No

Why This Works

Step 1: Check numbers from start to end

We look at each number in the given range one by one to test if it is prime.

Step 2: Test divisibility up to square root

To check if a number is prime, we only test divisibility up to its square root because any larger factor would have a smaller matching factor.

Step 3: Print prime numbers

If a number is not divisible by any number in the test range, it is prime and printed.

Alternative Approaches

Sieve of Eratosthenes

c

#include <stdio.h>
#include <string.h>

int main() {
    int start = 1, end = 20;
    int sieve[end+1];
    memset(sieve, 1, sizeof(sieve));
    sieve[0] = sieve[1] = 0;
    for (int i = 2; i*i <= end; i++) {
        if (sieve[i]) {
            for (int j = i*i; j <= end; j += i) {
                sieve[j] = 0;
            }
        }
    }
    for (int i = start; i <= end; i++) {
        if (sieve[i]) printf("%d ", i);
    }
    return 0;
}

This method is faster for large ranges but uses extra memory to store the sieve array.

Check divisibility only by primes

c

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

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

int main() {
    int start = 1, end = 20;
    for (int num = start; num <= end; num++) {
        if (isPrime(num)) printf("%d ", num);
    }
    return 0;
}

This reduces checks by skipping even numbers after 2, improving efficiency for larger numbers.

Complexity: O(n * sqrt(n)) time, O(1) space

Time Complexity

For each number in the range (n), we check divisibility up to its square root (sqrt(n)), resulting in O(n * sqrt(n)) time.

Space Complexity

The program uses constant extra space, only a few variables, so O(1) space.

Which Approach is Fastest?

The Sieve of Eratosthenes is faster for large ranges but uses O(n) space, while the simple divisibility check uses less memory but is slower.

Approach	Time	Space	Best For
Simple divisibility check	O(n * sqrt(n))	O(1)	Small ranges or memory-limited environments
Sieve of Eratosthenes	O(n log log n)	O(n)	Large ranges where speed is important
Divisibility by odd numbers only	About half of O(n * sqrt(n))	O(1)	Moderate optimization without extra memory