A prime number program in C checks whether a given number is divisible by any number other than 1 and itself. The simplest way to write this is a loop that tests divisibility from 2 up to the number, and if no divisor is found, the number is prime. A more efficient version only checks divisors up to the square root of the number, which drastically reduces the number of iterations for larger inputs. Below, you will find complete, working C programs for every common approach, including loops, functions, recursion, and the optimized square root method, along with sample output and a full explanation of the logic.
The prime number check is one of the earliest logic-building programs taught right after loops and conditionals in C, alongside topics like arrays, loops, and functions that form the backbone of the language. It is also a regular fixture in college lab exams, coding assessments, and interview rounds, since it tests whether a student can reason about divisibility and write clean, efficient loop logic rather than just memorize syntax.
This guide walks through every method of checking and printing prime numbers in C, with tested code, output, and a breakdown of the logic behind each approach.
What is a Prime Number?
A prime number is a natural number greater than 1 that has exactly two factors: 1 and itself. In other words, a prime number cannot be evenly divided by any number other than 1 and the number itself.
If a number greater than 1 has more than two factors, it is called a composite number. For example, 6 is composite because it can be divided evenly by 1, 2, 3, and 6, not just 1 and 6.
The formal definition can be summarized as:
A number n (where n > 1) is prime if the only positive divisors of n are 1 and n.
Prime numbers form the building blocks of number theory, since every natural number greater than 1 can be expressed as a product of prime numbers, a concept known as the fundamental theorem of arithmetic. Beyond mathematics, prime numbers play a major role in computer science and security, particularly in cryptography, where the difficulty of factoring large prime products underpins encryption algorithms used to secure online communication.
Examples of Prime Numbers
The first several prime numbers are:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47
Let us verify a couple of these manually before writing any code:
| Number | Divisors | Prime? |
| 2 | 1, 2 | Yes |
| 4 | 1, 2, 4 | No |
| 7 | 1, 7 | Yes |
| 9 | 1, 3, 9 | No |
| 11 | 1, 11 | Yes |
| 15 | 1, 3, 5, 15 | No |
Notice that 2 is the only even prime number. Every other even number is divisible by 2, so it automatically has more than two factors and cannot be prime. This small observation becomes a useful shortcut when writing an efficient prime-checking program, as you will see later in this guide.
Prime Number Program in C
Let us start with the most common, beginner-friendly version, a program that checks whether a single number entered by the user is prime.
C Program to Check Prime Number
#include <stdio.h>
int main() {
int n, i, isPrime = 1;
printf(“Enter a positive integer: “);
scanf(“%d”, &n);
if (n <= 1) {
isPrime = 0;
} else {
for (i = 2; i <= n / 2; i++) {
if (n % i == 0) {
isPrime = 0;
break;
}
}
}
if (isPrime == 1)
printf(“%d is a prime number.\n”, n);
else
printf(“%d is not a prime number.\n”, n);
return 0;
}
Output
Enter a positive integer: 29
29 is a prime number.
Enter a positive integer: 15
15 is not a prime number.
How the Program Works
Let us break the program down step by step so the logic is completely clear:
- Variable initialization: isPrime is set to 1, treating the number as prime by default. This is commonly called a flag variable, and it will be flipped to 0 the moment a divisor is found.
- Handling edge cases: Numbers less than or equal to 1 are never prime, so the program immediately sets isPrime = 0 for those without running the loop at all.
- The loop: The for loop checks every number from 2 up to n / 2. If n is evenly divisible by any of these values (n % i == 0), the number cannot be prime, so isPrime is set to 0 and the loop exits early using break.
- Why check only up to n / 2: No number greater than n / 2 (other than n itself) can divide n evenly, so checking beyond that point would be wasted effort. Later in this guide, you will see an even faster version that checks only up to the square root of n.
- Final decision: After the loop finishes, the program simply checks the value of isPrime to decide which message to print.
This flag-based approach is the standard way most beginners are taught to check primality, and it forms the foundation for every other variation covered in this guide, including loops, functions, and recursion.
Algorithm to Check Prime Number in C
Before coding, it helps to write out the algorithm in plain steps:
Step 1: Start
Step 2: Declare variables n, i, and a flag variable isPrime
Step 3: Read the number n from the user
Step 4: If n is less than or equal to 1, mark it as not prime
Step 5: Otherwise, repeat steps 6 to 8 for i = 2 to n / 2
Step 6: If n is divisible by i, mark isPrime as 0
Step 7: Exit the loop immediately (no need to check further)
Step 8: Continue to the next value of i if no divisor was found
Step 9: If isPrime is still 1, print that n is prime
Step 10: Otherwise, print that n is not prime
Step 11: Stop
This algorithm is the blueprint for every prime-checking program in this guide, whether implemented with a for loop, a while loop, a function, or recursion. Once you can confidently convert this algorithm into working code, adapting it to other divisibility-based problems becomes much easier.
Prime Number Program in C Using for Loop
The for loop is the most natural choice here, since we already know the exact range of numbers to check. Here is a clean, standalone version:
#include <stdio.h>
int main() {
int n = 23;
int i, isPrime = 1;
for (i = 2; i <= n / 2; i++) {
if (n % i == 0) {
isPrime = 0;
break;
}
}
if (n <= 1) {
isPrime = 0;
}
if (isPrime)
printf(“%d is a prime number.\n”, n);
else
printf(“%d is not a prime number.\n”, n);
return 0;
}
Output:
23 is a prime number.
Why this works well: The for loop keeps the initialization, condition, and increment together in a single line, making the code compact and easy to trace. It is the preferred structure for interviews and lab exams because the loop bounds are explicit, which reduces the risk of writing an infinite loop by mistake.
Prime Number Program in C Using while Loop
If you prefer to control the loop condition manually, a while loop achieves the exact same result.
#include <stdio.h>
int main() {
int n, i = 2, isPrime = 1;
printf(“Enter a positive integer: “);
scanf(“%d”, &n);
if (n <= 1) {
isPrime = 0;
} else {
while (i <= n / 2) {
if (n % i == 0) {
isPrime = 0;
break;
}
i++;
}
}
if (isPrime)
printf(“%d is a prime number.\n”, n);
else
printf(“%d is not a prime number.\n”, n);
return 0;
}
Output:
Enter a positive integer: 17
17 is a prime number.
The logic here is identical to the for loop version, only the placement of the initialization (i = 2), condition (i <= n / 2), and increment (i++) differs. A common beginner mistake with while loops is forgetting to write i++ inside the loop body, which causes an infinite loop since the condition never becomes false. Always double check your increment statement whenever you switch from a for loop to a while loop.
Prime Number Program in C Using Function
Wrapping the prime-checking logic inside a function makes the code reusable and easier to plug into larger programs, a habit worth building early, since most real-world C programs are built out of small, well-structured functions.
#include <stdio.h>
int checkPrime(int n) {
if (n <= 1) return 0;
for (int i = 2; i <= n / 2; i++) {
if (n % i == 0)
return 0;
}
return 1;
}
int main() {
int n;
printf(“Enter a positive integer: “);
scanf(“%d”, &n);
if (checkPrime(n))
printf(“%d is a prime number.\n”, n);
else
printf(“%d is not a prime number.\n”, n);
return 0;
}
Output:
Enter a positive integer: 31
31 is a prime number.
Notice how the function returns 0 or 1 directly instead of relying on a separate flag variable in main(). This is a cleaner style once you are comfortable with functions, and it means checkPrime() can be called from anywhere in a larger program, such as inside a loop that prints all primes in a range, which is exactly what the next few sections build on.
Prime Number Program in C Using Recursion
Recursion offers a different way to express the same divisibility check, useful for practicing how a function can call itself while still tracking state through parameters.
#include <stdio.h>
int isPrimeRecursive(int n, int i) {
if (n <= 1)
return 0;
if (i == 1)
return 1;
if (n % i == 0)
return 0;
return isPrimeRecursive(n, i – 1);
}
int main() {
int n;
printf(“Enter a positive integer: “);
scanf(“%d”, &n);
if (isPrimeRecursive(n, n / 2))
printf(“%d is a prime number.\n”, n);
else
printf(“%d is not a prime number.\n”, n);
return 0;
}
Output:
Enter a positive integer: 19
19 is a prime number.
Here, isPrimeRecursive() takes two parameters, the number n being tested and the current divisor i, starting from n / 2 and counting down. The function has two base cases: if n is less than or equal to 1, it is not prime, and if i reaches 1 without finding a divisor, the number is confirmed prime. Every recursive call reduces i by one, moving the function closer to its base case. This is the same recursion pattern used to teach function calls and problem decomposition in other classic beginner programs, such as a Fibonacci series program in C.
One thing to keep in mind: recursion adds function call overhead compared to a simple loop, so for large numbers, the iterative approach remains the more efficient and commonly preferred choice in production code.
Print Prime Numbers from 1 to N in C
Instead of checking a single number, this program prints every prime number within a given range, from 1 up to a user-defined value n.
#include <stdio.h>
int checkPrime(int num) {
if (num <= 1) return 0;
for (int i = 2; i <= num / 2; i++) {
if (num % i == 0)
return 0;
}
return 1;
}
int main() {
int n;
printf(“Enter the value of N: “);
scanf(“%d”, &n);
printf(“Prime numbers from 1 to %d are: “, n);
for (int num = 2; num <= n; num++) {
if (checkPrime(num)) {
printf(“%d “, num);
}
}
return 0;
}
Output:
Enter the value of N: 30
Prime numbers from 1 to 30 are: 2 3 5 7 11 13 17 19 23 29
This program simply loops through every number from 2 to n and calls checkPrime() on each one, printing it only if the function confirms it is prime. Starting the outer loop from 2 instead of 1 is intentional, since 1 is never a prime number, and skipping it avoids an unnecessary function call.
Find Prime Numbers Between Two Numbers in C
A slight variation of the previous program lets the user specify both a lower and upper bound, which is a common requirement in real assignments and interview questions.
#include <stdio.h>
int checkPrime(int num) {
if (num <= 1) return 0;
for (int i = 2; i <= num / 2; i++) {
if (num % i == 0)
return 0;
}
return 1;
}
int main() {
int low, high;
printf(“Enter the lower bound: “);
scanf(“%d”, &low);
printf(“Enter the upper bound: “);
scanf(“%d”, &high);
printf(“Prime numbers between %d and %d are: “, low, high);
for (int num = low; num <= high; num++) {
if (checkPrime(num)) {
printf(“%d “, num);
}
}
return 0;
}
Output:
Enter the lower bound: 10
Enter the upper bound: 50
Prime numbers between 10 and 50 are: 11 13 17 19 23 29 31 37 41 43 47
The only real difference from the previous program is that the loop now starts at low instead of a fixed value, giving the user full control over the range being checked. This pattern, reusing a working function across slightly different problems, is exactly the kind of modular thinking that makes larger C programs easier to build and debug.
Check Prime Number Using √N in C
The programs so far check divisibility up to n / 2, which works correctly but does more work than necessary. A faster method only checks divisors up to the square root of n, because if n has a factor larger than its square root, it must also have a corresponding factor smaller than the square root, so checking beyond that point is redundant.
#include <stdio.h>
#include <math.h>
int checkPrimeOptimized(int n) {
if (n <= 1) return 0;
if (n == 2) return 1;
if (n % 2 == 0) return 0;
for (int i = 3; i <= sqrt(n); i += 2) {
if (n % i == 0)
return 0;
}
return 1;
}
int main() {
int n;
printf(“Enter a positive integer: “);
scanf(“%d”, &n);
if (checkPrimeOptimized(n))
printf(“%d is a prime number.\n”, n);
else
printf(“%d is not a prime number.\n”, n);
return 0;
}
Output:
Enter a positive integer: 97
97 is a prime number.
This version includes a few smart optimizations worth noting:
- It handles 2 as a special case, since it is the only even prime number.
- It immediately eliminates every other even number with n % 2 == 0, skipping half of all possible divisors right away.
- The loop then checks only odd divisors, starting from 3, incrementing by 2 each time (i += 2), and stopping once i exceeds the square root of n.
For large values of n, this optimization makes a significant difference. Checking divisors up to n / 2 for a number like 10 million means up to 5 million iterations, while checking up to its square root means roughly 3,162 iterations, a massive reduction in work. This is a good example of why understanding time complexity, covered later in this guide, matters even for a problem as simple as checking a single number.
Prime Number Program in C Without Using a Flag
Some interview questions specifically ask you to avoid using a flag variable, relying instead on return statements or break combined with a loop counter to determine the result. Here is a version that skips the isPrime flag entirely by using a function’s return value directly:
#include <stdio.h>
int isPrime(int n) {
if (n <= 1)
return 0;
for (int i = 2; i <= n / 2; i++) {
if (n % i == 0)
return 0;
}
return 1;
}
int main() {
int n;
printf(“Enter a positive integer: “);
scanf(“%d”, &n);
printf(“%d is %sa prime number.\n”, n, isPrime(n) ? “” : “not “);
return 0;
}
Output:
Enter a positive integer: 12
12 is not a prime number.
Here, the function exits immediately with return 0 the moment a divisor is found, and reaches return 1 only if the loop completes without finding one. There is no separate flag variable being updated and checked afterward, the return statement itself communicates the result. This style is generally considered cleaner in professional code, since it avoids extra state and makes the function’s intent immediately clear from its return value alone.
Prime vs Composite Numbers
Understanding the distinction between prime and composite numbers is essential before writing any prime-checking logic, and it is a frequent point of confusion for beginners.
| Aspect | Prime Number | Composite Number |
| Definition | Has exactly two factors, 1 and itself | Has more than two factors |
| Examples | 2, 3, 5, 7, 11, 13 | 4, 6, 8, 9, 10, 12 |
| Smallest example | 2 | 4 |
| Divisibility | Cannot be evenly divided by any number other than 1 and itself | Can be evenly divided by at least one number other than 1 and itself |
| Special cases | 2 is the only even prime number | 1 is neither prime nor composite |
The number 1 deserves special attention: it is neither prime nor composite, because the definition of a prime number requires exactly two distinct factors, while 1 has only one factor, itself. This is why every prime-checking program in this guide explicitly handles n <= 1 as a separate case rather than letting the loop logic decide it.
Common Mistakes in Prime Number Programs in C
Even though checking for a prime number is a simple problem, beginners run into the same handful of errors repeatedly. Watch out for these:
- Forgetting to handle numbers less than or equal to 1. Without an explicit check, a loop-based program may incorrectly treat 0, 1, or negative numbers as prime, since the loop body might never execute for very small values.
- Starting the loop from 1 instead of 2. Since every number is divisible by 1, starting the divisor check from i = 1 will always find a match immediately and incorrectly mark every number as not prime.
- Checking divisors all the way up to n instead of n / 2 or √n. This does not produce incorrect results, but it wastes processing time, especially for larger numbers, and shows a lack of understanding of the underlying math during interviews.
- Forgetting the break statement. Without break, the loop continues checking every remaining value even after a divisor has already been found, which works correctly but is unnecessarily inefficient.
- Off-by-one errors in loop conditions. Using i < n / 2 instead of i <= n / 2 can cause the loop to miss a valid divisor in certain edge cases, leading to incorrect results.
- Incorrectly treating 2 as not prime. Since 2 is the only even prime number, programs that add a blanket “skip all even numbers” optimization without first checking for n == 2 will incorrectly mark it as not prime.
- Missing base cases in the recursive version. Forgetting to handle n <= 1 or the terminating condition i == 1 in the recursive approach can lead to incorrect results or, in more complex recursive designs, a stack overflow.
Avoiding these pitfalls does more than just fix a single program, it builds the habit of thinking through edge cases carefully, which carries over to every other conditional and loop-based problem you write in C.
Time and Space Complexity
Understanding complexity helps explain why the square root optimization matters, and it is a useful, hands-on example of time complexity analysis for beginners.
| Approach | Time Complexity | Space Complexity | Explanation |
| Check up to n | O(n) | O(1) | Tests every number from 2 to n, which is correct but unnecessarily slow. |
| Check up to n / 2 | O(n) | O(1) | Still linear time, since n / 2 is still proportional to n, just with a smaller constant factor. |
| Check up to √n | O(√n) | O(1) | Significantly faster for large numbers, since the number of iterations grows much more slowly than n itself. |
| Recursive version | O(n) | O(n) | Same linear time as the iterative version, but uses additional space for the recursive call stack. |
| Print primes from 1 to N | O(N × √N) | O(1) | Each number up to N is checked individually using the optimized method, so the total work scales with both N and the square root check. |
Why this matters: For a small number like 97, the difference between checking up to n / 2 (48 iterations) and up to √n (about 9 iterations) may seem negligible. But for a number like 10,000,019, checking up to n / 2 requires roughly 5 million iterations, while checking up to √n requires only about 3,162. This kind of hands-on comparison is exactly why the prime number problem is such a popular teaching tool for complexity analysis, alongside other classic beginner programs like a Fibonacci series program in C, where the same iterative versus recursive trade-off shows up again.
For applications that need to check primality for very large numbers repeatedly, more advanced techniques like the Sieve of Eratosthenes (which precomputes all primes up to a limit in O(n log log n) time) or probabilistic tests like the Miller-Rabin primality test are used instead, both of which are worth exploring once you are comfortable with the fundamentals covered here.
FAQs
What is a prime number in C?
In C programming, a prime number check refers to a program that determines whether a given integer has exactly two factors, 1 and itself. This is typically implemented using a loop that tests divisibility from 2 up to either n / 2 or the square root of n, and if no divisor is found in that range, the number is confirmed as prime.
How do you check a prime number in C?
To check a prime number in C, first handle the edge case where the number is less than or equal to 1, since such numbers are never prime. Then use a loop to test whether the number is divisible by any integer from 2 up to n / 2 (or more efficiently, up to the square root of n). If any of these values divides the number evenly, it is not prime. If the loop completes without finding a divisor, the number is prime. The complete working code is provided in the “C Program to Print Fibonacci Series” section above, and prime-number specific versions are covered throughout this guide, starting with “Prime Number Program in C.”
How do you print prime numbers from 1 to N?
Loop through every number from 2 to N, and for each number, run a prime-checking function that tests divisibility up to n / 2 or its square root. If the function confirms the number is prime, print it before moving to the next number in the range. The complete code and sample output are available in the “Print Prime Numbers from 1 to N in C” section above.
Is 1 a prime number?
No, 1 is not a prime number. By definition, a prime number must have exactly two distinct positive factors, 1 and itself. The number 1 has only one factor, itself, so it does not meet the definition. It is also not classified as a composite number, since composite numbers require more than two factors. This is why every prime-checking program in this guide explicitly excludes numbers less than or equal to 1 before running the divisibility loop.
Is 2 a prime number?
Yes, 2 is a prime number, and it is the only even prime number. Its only two factors are 1 and 2 itself, satisfying the definition of a prime number. Every other even number greater than 2 is divisible by 2 in addition to 1 and itself, giving it more than two factors, which is why 2 stands out as a special case in optimized prime-checking algorithms that skip even numbers after handling 2 separately.
Practice Programs Based on Prime Number Logic
Once you are comfortable with the standard prime-checking program, try these variations to deepen your understanding of loops, functions, and recursion in C:
- Count the total number of prime numbers within a given range instead of printing them individually.
- Find the sum of all prime numbers between two given numbers.
- Check whether a number is a twin prime, meaning it differs by exactly 2 from another prime number, such as 11 and 13.
- Print the first N prime numbers, rather than all primes within a fixed numeric range.
- Implement the Sieve of Eratosthenes in C to efficiently generate all prime numbers up to a large limit, and compare its performance against the trial division method covered in this guide.
- Check whether a number is a prime palindrome, meaning it reads the same forwards and backwards and is also prime, such as 131 or 151.
- Combine prime-checking logic with an array to store and later sort or search through all primes found within a range.
- Write a menu-driven C program that lets the user choose between checking a single number, printing primes up to N, or finding primes between two numbers, reinforcing the modular, function-based coding style demonstrated throughout this guide.
Practicing these variations is one of the best ways to move from simply copying a working prime number program to genuinely understanding loops, functions, and conditional logic well enough to solve new problems independently, which is exactly the kind of hands-on, problem-solving skill that Codegnan’s C programming training is built around. If you want to continue strengthening your logic-building skills, the Armstrong number program is another classic beginner exercise that uses the same digit manipulation and loop patterns you have practiced here, and exploring a set of beginner C programming projects is a natural next step once these fundamentals feel solid.
