Finding prime numbers within a given range is a common exercise in C programming. A prime number is a number greater than 1 that is divisible only by 1 and itself. Numbers like 2, 3, 5, 7, 11, and 13 are prime, while numbers such as 4, 6, 8, 9, and 12 are not. Printing all prime numbers between two intervals means that instead of checking just one number, we will generate a series of numbers and check each one individually.
with hands-on learning.
get the skills and confidence to land your next move.
This type of program is important because it introduces you to nested logic. You will learn how to combine loops and conditional statements to solve more complex problems. It also shows how to handle user input for ranges and gives practice with mathematical conditions that form the basis of many algorithms. By the end of this tutorial, you will know how to write a C program that asks for two intervals and prints all the prime numbers between them, while also understanding why each part of the program works the way it does.
Understanding the Problem
Let us first understand the task clearly. If the user enters two numbers, for example 10 and 30, the program should print all the prime numbers between these values. That means the output should be 11, 13, 17, 19, 23, and 29. To do this, we need to check every number between 10 and 30 and test whether each number is prime or not.
The steps are simple in logic but require careful implementation. First, we take the starting point and the ending point from the user. Then we use a loop to go through every number in this range. For each number, we check if it is prime using the same method as before — by testing divisibility. If the number is prime, we print it. If it is not, we skip it and continue with the next number.
C Program to Print All Prime Numbers Between Two Intervals
Here is the basic program:
#include <stdio.h>
int main() {
int start, end, i, j, isPrime;
printf("Enter two numbers (intervals): ");
scanf("%d %d", &start, &end);
printf("Prime numbers between %d and %d are:\n", start, end);
for (i = start; i <= end; i++) {
if (i <= 1) {
continue; // numbers less than or equal to 1 are not prime
}
isPrime = 1; // assume the number is prime
for (j = 2; j <= i / 2; j++) {
if (i % j == 0) {
isPrime = 0;
break;
}
}
if (isPrime == 1) {
printf("%d ", i);
}
}
printf("\n");
return 0;
}Let us carefully understand how this program works. We begin with #include <stdio.h> which allows us to use input and output functions. Inside the main() function, we declare variables: start and end for the interval, i and j for loop counters, and isPrime as a flag to track whether a number is prime.
The program first asks the user to enter two numbers. These numbers form the lower and upper bounds of our interval. For example, if the user enters 10 and 30, those become the values of start and end.
We then use a for loop that starts at i = start and continues up to end. For each value of i, we check if it is prime. Numbers less than or equal to 1 are skipped immediately because they are not prime. For all other numbers, we assume the number is prime by setting isPrime = 1.
Next, we use another loop with variable j that runs from 2 up to i / 2. For each value of j, we check if i % j == 0. If the number divides evenly, it is not prime. In that case, we set isPrime = 0 and break out of the loop. If no such divisor is found, then the number remains prime.
Finally, if isPrime is still 1, we print the number as prime. This continues until all numbers in the interval are checked. At the end, we print a new line to keep the output clean.
Optimizing the Program with Square Root
The above program works well, but for larger intervals it may be slow. Instead of checking divisibility up to i / 2, we can check only up to the square root of i. This reduces the number of checks and makes the program faster.
Here is the optimized version:
#include <stdio.h>
#include <math.h>
int main() {
int start, end, i, j, isPrime;
printf("Enter two numbers (intervals): ");
scanf("%d %d", &start, &end);
printf("Prime numbers between %d and %d are:\n", start, end);
for (i = start; i <= end; i++) {
if (i <= 1) {
continue;
}
isPrime = 1;
for (j = 2; j <= sqrt(i); j++) {
if (i % j == 0) {
isPrime = 0;
break;
}
}
if (isPrime == 1) {
printf("%d ", i);
}
}
printf("\n");
return 0;
}In this version, we add #include <math.h> at the top to use the sqrt() function. Inside the loop, instead of checking divisibility up to i / 2, we check only up to sqrt(i). This makes the program more efficient without changing the result. For example, if the number is 29, we only check up to sqrt(29) which is around 5.38, instead of checking all the way up to 14.
Common Beginner Mistakes
When writing a prime number program, beginners often make these mistakes:
- Not handling numbers less than or equal to 1. If these cases are skipped, the program may incorrectly classify them as prime.
- Writing the loop condition incorrectly, such as using
j <= iinstead ofj <= i / 2orj <= sqrt(i). This makes every number appear as not prime, since every number is divisible by itself. - Forgetting to reset the
isPrimeflag for each new number. If it’s declared once outside the loop and not updated properly, the program will give wrong results.
To avoid these issues, always handle small numbers separately, use correct loop boundaries, and reset the isPrime flag inside the outer loop for every new number tested.
FAQs
Q1: Can the start of the interval be greater than the end?
No, normally the start should be smaller than the end. If the user enters them the other way, you can swap the values in your program to make it work.
Q2: Is 1 a prime number?
No, 1 is not prime. Prime numbers are defined as numbers greater than 1 that are divisible only by 1 and themselves.
Q3: Can I use a while loop instead of a for loop?
Yes, you can use a while loop for both the outer and inner loops. The logic remains the same, only the loop style changes.
Q4: Why use square root optimization?
Using the square root reduces the number of iterations when checking for divisibility, which makes the program run faster, especially for larger numbers.
Conclusion
Printing all prime numbers between two intervals is an excellent programming exercise. It teaches you how to work with ranges, how to use nested loops, and how to apply mathematical concepts in code. You also practice writing efficient logic by using square root optimization. Once you are comfortable with this program, you can extend the idea to generate prime numbers in larger ranges, or even move on to advanced problems such as finding twin primes and prime factorization.
References & Additional Resources
- Kernighan, Brian W., and Dennis M. Ritchie. The C Programming Language. 2nd Edition, Prentice Hall, 1988.
- Wikipedia: Prime number – Overview of what prime numbers are and computational methods like trial division and primality testing.
- GeeksforGeeks: Prime Numbers in C – Tutorial on writing C code to list prime numbers between two intervals.
- cplusplus.com: cmath (math.h) – Reference listing common math functions in C/C++, including
sqrtused for checking primality efficiently. - Stack Overflow: Prime Number Algorithms – Discussion on improving prime-checking logic in C, including the use of
i * i <= numberand optimizing with 6*k ± 1 form.
