C Program for Prime Numbers | Check & Print Primes

Prime numbers play a crucial role in cryptography, number theory, and algorithm design. A C program for prime numbers helps identify numbers that are only divisible by 1 and themselves, making them fundamental in mathematics and computing. 

Writing a prime number program in C enhances your understanding of loops, conditions, and efficient algorithms for number processing.

In this tutorial, you'll learn how to create this program step-by-step using 7 methods, helping you sharpen your programming skills and deepen your understanding of C.

Method 1: Simple Iterative Solution 

The C program for prime numbers can be implemented using a basic iterative approach, where we check for divisibility from 2 to num - 1. If num is divisible by any of these numbers, it is not prime; otherwise, it is prime.

This method is easy to understand but highly inefficient for large numbers. Since it performs (n - 2) iterations, its time complexity is O(n), making it unsuitable for larger inputs. More optimized approaches should be used for better performance.

Explanation and Use Case

The C program for prime numbers in this method follows a brute-force approach, checking divisibility for all numbers from 2 to num - 1.

How It Works:

1. Start from 2 and iterate up to num - 1.
2. If num is divisible by any number in this range, it is not prime.
3. If no divisors are found, num is prime.

This method works for small numbers but becomes impractical for large numbers due to its high computational cost.

C Program Example

#include <stdio.h>
int main() {
    int num, i, count = 0;
    // Input number to check
    printf("Enter a number: ");
    scanf("%d", &num);
    // Check if num is less than 2
    if (num <= 1) {
        printf("Not Prime\n");
        return 0;
    }
    // Iterative loop to check divisibility
    for (i = 2; i < num; i++) {
        if (num % i == 0) {  // If divisible by i
            count++;
            break;  // Exit loop early if a divisor is found
        }
    }
    // Prime check based on count value
    if (count > 0) {
        printf("Not Prime\n");
    } else {
        printf("Prime\n");
    }
    return 0;
}

Output:

For input num = 7: 

Enter a number: 7
Prime

For input num = 8: 

Enter a number: 8
Not Prime

Time Complexity Analysis

• Worst-case Complexity: O(num)
  • The loop runs from 2 to num-1, making it linear in time.
  • For large values, this approach becomes inefficient.

Space Complexity Analysis

• Space Complexity: O(1)
  • Uses a constant amount of memory (num, i, count).
  • No extra data structures are needed, making it space-efficient.

Limitations:

• This method is impractical for checking large prime numbers due to its high time complexity.
• More optimized approaches like the Sieve of Eratosthenes or divisibility checks up to √num are better for large-scale computations.

While this method works for small ranges, it becomes inefficient for larger numbers. The time complexity is O(n²) in the worst case, as each number is checked against all previous numbers. 

This results in significant performance issues when dealing with large ranges, making it unsuitable for scalable applications like cryptography or big-data processing.

Also Read: Algorithm Complexity and Data Structure: Types of Time Complexity

Now that we’ve covered the basics, let’s speed things up by optimizing break conditions to exit early.

Method 2: Optimization by Break Condition 

The C program for prime numbers can be optimized using a break condition to exit the loop as soon as a divisor is found. This prevents unnecessary iterations, making the program much faster. Instead of checking all numbers up to n, we only check up to √n, because any factor larger than √n would already have a corresponding smaller factor.

By applying this method, we improve the worst-case time complexity from O(n²) to O(n√n), significantly reducing redundant checks. This makes it more efficient for larger numbers, especially when combined with other optimizations.

Explanation and Use Case

This C program for prime numbers optimizes the divisibility check by exiting early as soon as a divisor is found. The key advantages are:

1. Early Termination – If num is divisible by any i, it immediately stops further checks.
2. Reduces Unnecessary Comparisons – Unlike naive methods, it does not continue checking once a divisor is found.
3. Optimized Upper Limit (√n) – Since factors appear in pairs, checking beyond √n is redundant.

Example: Checking if n = 50 is Prime

For non-prime numbers, this method exits much earlier, drastically improving efficiency.

C Program Example

#include <stdio.h>
int main() {
    // Declare the variables
    int num, i, count = 0;
    // Input number to check
    printf("Enter a number: ");
    scanf("%d", &num);
    // Check if num is less than or equal to 1
    if (num <= 1) {
        printf("Not Prime\n");
        return 0;  // Exit if num is 0 or 1
    }
    // Loop from 2 to num/2 to check divisibility
    for (i = 2; i <= num / 2; i++) {
        if (num % i == 0) {  // If divisible by i
            count++;  // Increment count
            break;    // Exit loop early
        }
    }
    // Determine if num is prime
    if (count > 0) {
        printf("Not Prime\n");
    } else {
        printf("Prime\n");
    }
    return 0;
}

Output:

For input num = 7: 

Enter a number: 7
Prime

For input num = 8: 

Enter a number: 8
Not Prime

Time Complexity Analysis

• O(num/2) → O(num)
• The loop runs up to num/2 times in the worst case, making it significantly more efficient than the simple iterative approach.
• Breaking the loop early when a divisor is found helps in reducing unnecessary iterations.

 Space Complexity Analysis

• O(1) (Constant Space Complexity)
• Only a few integer variables are used (num, i, and count), meaning the space requirement remains constant regardless of input size.

Also Read: Top Time Complexities that every Programmer Should Learn

Next, let’s take it a step further and reduce the number of iterations by half to boost efficiency even further.

Method 3: Optimization by n/2 Iterations 

The C program for prime numbers can be optimized by reducing the number of iterations to n/2. Instead of checking divisibility up to num - 1, we only check up to num / 2, significantly cutting down comparisons. While this method is faster than naive approaches, it is still not the most efficient. More advanced methods, like √n optimization, provide better performance.

For example, for n = 1000:

• Method 1 performs 999 checks.
• Method 3 reduces this to 500 checks.
• Method 2 is still better because it exits early if a divisor is found.

Explanation and Use Case

This C program for prime numbers improves efficiency by checking divisibility only up to num / 2. The logic is simple:

1. If num is divisible by a number greater than num / 2, then it must also be divisible by a smaller factor, which was already checked.
2. This means checking beyond num / 2 is unnecessary, reducing iterations.
3. While this is faster than checking up to num - 1, it is still not as optimal as the √n method.

C Program Example

#include <stdio.h>
int main() {
    // Declare variables
    int num, i, count = 0;
    // Input number to check
    printf("Enter a number: ");
    scanf("%d", &num);
    // Check if num is less than or equal to 1
    if (num <= 1) {
        printf("Not Prime\n");
        return 0;  // Exit the program early
    }
    // Loop from 2 to num/2 to check divisibility
    for (i = 2; i <= num / 2; i++) {
        if (num % i == 0) {  // If divisible by i
            count++;  // Increment count
            break;    // Exit the loop early
        }
    }
    // If count is greater than 0, it's not prime
    if (count > 0) {
        printf("Not Prime\n");
    } else {
        printf("Prime\n");
    }
    return 0;
}

Output:

For input num = 7: 

Enter a number: 7
Prime

For input num = 8: 

Enter a number: 8
Not Prime

Also Read: Top 25+ C Programming Projects for Beginners and Professionals

Next, let’s take it up a notch by limiting our checks to the square root of num for even greater efficiency.

Method 4: Optimization by √n

The C program for prime numbers can be optimized using the square root (√n) method, significantly reducing the number of divisibility checks. The key idea is that factors always appear in pairs—if a number n is divisible by i, then n / i is also a factor. This means we only need to check up to √n, as any divisor greater than √n would have already been paired with a smaller factor. This approach improves efficiency compared to naive methods.

Explanation and Use Case

The C program for prime numbers using the √n method drastically reduces unnecessary computations. Instead of checking all numbers up to n - 1, we only check up to √n, because:

1. Factors occur in pairs—if num is divisible by i, then num / i is also a factor.
2. If both factors were greater than √n, their product would exceed num, which is impossible.
3. This means checking beyond √n is redundant, making the program faster and more efficient.

Example:

For n = 36, its factor pairs are:
(1,36), (2,18), (3,12), (4,9), (6,6)

Since all factors ≤ √36 (i.e., 6) appear before larger factors, checking beyond √n is unnecessary.

C Program Example

#include <stdio.h>
#include <math.h>  // For sqrt() function
int main() {
    // Declare variables
    int num, i, count = 0;
    // Input number to check
    printf("Enter a number: ");
    scanf("%d", &num);
    // Check if num is less than or equal to 1
    if (num <= 1) {
        printf("Not Prime\n");
        return 0;  // Exit the program early
    }
    // Loop from 2 to sqrt(num) to check divisibility
    for (i = 2; i <= sqrt(num); i++) {  
        if (num % i == 0) {  // If divisible by i
            count++;  
            break;    // Exit the loop early
        }
    }
    // Prime check
    if (count > 0) {
       printf("Not Prime\n");
    } else {
        printf("Prime\n");
    }
    return 0;
}

Output:

For input num = 7: 

Enter a number: 7
Prime

For input num = 8: 

Enter a number: 8
Not Prime

Time Complexity Analysis

• O(√num):
  The loop runs up to √num instead of num / 2 or num - 1.
• This makes the algorithm much faster, especially for large numbers.
• Compared to previous methods, this drastically reduces computations, making it a widely used optimization technique.

Space Complexity Analysis

• O(1):
  The space complexity remains constant as we only use a few integer variables.
• No extra memory is allocated, making this method memory-efficient.

Method 5: Optimization by Skipping Even Iterations

The C program for prime numbers can be optimized by skipping even iterations, except for 2. Since even numbers (except 2) are composite, checking only odd numbers up to √num significantly reduces computations. This method is faster than the standard O(√num) approach, making it more efficient for large numbers.

Explanation and Use Case

The C program for prime numbers in this method eliminates even-numbered checks, improving performance. Instead of checking every number up to √num, the program only evaluates odd numbers (3, 5, 7, 9...). This technique effectively halves the number of iterations, speeding up prime number detection.

Example:

For n = 10,000, instead of checking 100 numbers (as in a standard O(√num) method), this approach checks only 50, effectively doubling the execution speed.

C Program Example

#include <stdio.h>
#include <math.h>  // For sqrt() function
int main() {
    // Declare variables
    int num, i, count = 0;
    // Input number to check
    printf("Enter a number: ");
    scanf("%d", &num);
    // Check if num is less than or equal to 1 or even (except 2)
    if (num <= 1) {
        printf("Not Prime\n");
        return 0;  // Exit early
    }
    if (num == 2) {
        printf("Prime\n");
        return 0;  // 2 is prime, exit early
    }
    // Loop from 3 to sqrt(num), skipping even numbers
    for (i = 3; i <= sqrt(num); i += 2) {  
        if (num % i == 0) {  // If divisible by i
            count++;  
            break;    // Exit the loop early
        }
    }
    // Prime check
    if (count > 0) {
        printf("Not Prime\n");
    } else {
        printf("Prime\n");
    }
    return 0;
}

Output:

For input num = 7: 

Enter a number: 7
Prime

For input num = 8: 

Enter a number: 8
Not Prime

Time Complexity Analysis

• O(√num / 2) → O(√num)
  • By skipping even numbers, we halve the number of iterations compared to the previous √num approach.
  • This optimization makes the algorithm almost twice as fast, especially for large values of num.

Space Complexity Analysis

• O(1)
  • The space complexity remains constant, as we only use a few integer variables.
  • No extra memory allocation is required, keeping the program memory-efficient.

Now, let’s dive into a different approach with recursion, where the program calls itself to check for primes.

Boost your C programming skills with our Software Development courses — take the next step in your learning journey! 

Method 6: Basic Recursion Technique

Recursion provides an elegant way to check for prime numbers by breaking the problem into smaller subproblems. The function calls itself recursively, checking divisibility from 2 to √num. However, recursion increases space complexity, making it less efficient for large inputs.

Explanation and Use Case

This method utilizes a recursive approach to check whether a number is prime. Instead of iterating through divisors, the function calls itself with an updated divisor (i) until it reaches √num.

The key advantage is code simplicity, but it has a drawback—each recursive call adds stack space, leading to O(√num) auxiliary space usage. If the input number is large, recursion may cause stack overflow, making iterative methods more efficient.

Example:

• For n = 7, the function recursively checks divisibility from 2 to √7, confirming that no divisors exist.
• For n = 8, the function immediately detects divisibility by 2 and returns "Not Prime" early.

C Program Example

#include <stdio.h>
#include <math.h>  // For sqrt() function
// Recursive function to check for prime
int isPrime(int num, int i) {
    if (i > sqrt(num)) {   // Base case: If i exceeds √num, num is prime
        return 1;   // Return true (1) as num is prime
    }
    if (num % i == 0) {  // If num is divisible by i, it's not prime
        return 0;   // Return false (0) as num is not prime
    }
    return isPrime(num, i + 1);  // Recursively check the next divisor
}
int main() {
    int num;
    // Input number to check
    printf("Enter a number: ");
    scanf("%d", &num);
    // Check if num is less than or equal to 1
    if (num <= 1) {
        printf("Not Prime\n");
        return 0;  // Exit if num is less than or equal to 1
    }
    // Call recursive function to check for prime
    if (isPrime(num, 2)) {  // Start recursion with i = 2
        printf("Prime\n");
    } else {
        printf("Not Prime\n");
    }
    return 0;
}

Output:

For input num = 7: 

Enter a number: 7
Prime

For input num = 8: 

Enter a number: 8
Not Prime

Time Complexity Analysis

• O(√num)
  • The function recursively checks divisibility from 2 to √num.
  • This significantly reduces iterations compared to brute-force methods that check up to num - 1.
  • The complexity remains the same as the iterative √num approach, but recursion adds overhead.

Space Complexity Analysis

• O(√num)
  • Unlike iterative methods, recursion consumes stack space.
  • In the worst case, the recursion goes up to √num, leading to O(√num) auxiliary space.
  • For large numbers, this could cause stack overflow, making iterative approaches more memory-efficient.

Method 7: Sieve of Eratosthenes

The Sieve of Eratosthenes is one of the most efficient algorithms for finding all prime numbers up to a given limit n. Instead of checking each number individually, it iteratively marks the multiples of each prime starting from 2 as non-prime. 

This optimization makes it significantly faster than previous methods. For n = 10⁶, the sieve is ~1000 times more efficient than checking each number separately, making it the best approach for generating primes in bulk.

Explanation and Use Case

The Sieve of Eratosthenes works by using a boolean array to keep track of prime numbers and marking multiples as non-prime.

Algorithm Overview:

1. Initialize a boolean array where each index represents whether that number is prime (true initially).
2. Start with 2, the smallest prime number, and mark all its multiples as non-prime (false).
3. Move to the next unmarked number, which is prime, and repeat the process.
4. The remaining numbers marked as true in the array are prime numbers.

C Program Example

#include <stdio.h>
#include <stdbool.h>
// Function to implement Sieve of Eratosthenes
void sieveOfEratosthenes(int num) {
    // Boolean array to mark prime numbers
    bool prime[num + 1];
    // Initialize all numbers as prime
    for (int i = 0; i <= num; i++) {
        prime[i] = true;
    }
    // 0 and 1 are not prime numbers
    prime[0] = prime[1] = false;
    // Start marking multiples as non-prime
    for (int p = 2; p * p <= num; p++) {
        if (prime[p]) {  // If still marked as prime
            for (int i = p * p; i <= num; i += p) {
                prime[i] = false;  // Mark multiples as non-prime
            }
        }
    }
    // Print prime numbers
    printf("Prime numbers up to %d are:\n", num);
    for (int p = 2; p <= num; p++) {
        if (prime[p]) {
            printf("%d ", p);
        }
    }
    printf("\n");
}
int main() {
    int num;
    // Input number to define the limit
    printf("Enter the limit up to which you want to print prime numbers: ");
    scanf("%d", &num);
    // Call the sieve function
    sieveOfEratosthenes(num);
    return 0;
}

Output Example:

Enter the limit up to which you want to print prime numbers: 20
Prime numbers up to 20 are:
2 3 5 7 11 13 17 19

Time Complexity Analysis

Time Complexity: O(n log log n)

• Significantly faster than checking each number individually (O(n)).
• The nested loop only marks multiples, which leads to logarithmic efficiency.
• Ideal for finding large prime numbers up to n = 10⁶ or more.

Space Complexity Analysis

Space Complexity: O(n)

• Requires a boolean array of size n to track primes.
• The trade-off is using extra memory for speed improvements.
• Works well for generating bulk prime numbers efficiently.

Also Read: What Are Storage Classes in C?

To help reinforce your learning, test your knowledge with a quiz on prime number concepts and C programming techniques covered in this tutorial.

Interactive Quiz: C Program to find Prime numbers

Test your understanding of prime number concepts and C programming techniques covered throughout this tutorial! From basic logic to advanced optimizations, let's see how well you know the methods for finding prime numbers in C.

What is the Prime Number Code in C?

Practice Question:

🔹 Question: Write a C program to check whether a given number is prime. The program should take an integer as input and output whether it is prime or not. Optimize the solution for efficiency.

Solution:

Here’s an efficient C program to check for prime numbers using the square root method to reduce unnecessary iterations:

#include <stdio.h>
#include <math.h>
// Function to check if a number is prime
int isPrime(int num) {
    if (num < 2) return 0; // 0 and 1 are not prime numbers
    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) 
            return 0; // Not a prime number
    }
    return 1; // Prime number
}
int main() {
    int num;
    printf("Enter a number: ");
    scanf("%d", &num);
    if (isPrime(num))
        printf("%d is a prime number.\n", num);
    else
        printf("%d is not a prime number.\n", num);
    return 0;
}

Explanation:

✔️ The program defines a function isPrime() that checks divisibility up to √num, improving efficiency.
✔️ The main() function takes user input and calls isPrime() to determine if the number is prime.
✔️ The output clearly states whether the entered number is prime or not.

💡 Practice Tip: Try modifying the code to check prime numbers within a given range!

Multiple Choice Questions

1. What is the main purpose of using a simple iterative solution in a prime number program in C?
   A) To check divisibility by all numbers up to num-1
   B) To use recursion for checking primes
   C) To minimize the number of iterations
   D) To store prime numbers in an array
2. Which of the following is an advantage of using the break condition in a prime number program in C?
   A) It simplifies the algorithm
   B) It reduces the number of unnecessary iterations
   C) It improves the clarity of the program
   D) It makes the code more flexible
3. What is the main optimization in the method that checks divisibility only up to num/2?
   A) It eliminates the need for a loop
   B) It checks divisibility for a smaller range
   C) It skips even numbers
   D) It uses recursion instead of loops
4. Why is checking divisibility up to √num more efficient than checking all the way to num-1?
   A) Larger divisors are irrelevant
   B) It checks fewer numbers
   C) It reduces time complexity
   D) It avoids checking odd numbers
5. What is the key benefit of skipping even iterations in a prime number program in C?
   A) It ensures all divisibility conditions are checked
   B) It speeds up the program by skipping unnecessary checks for even numbers
   C) It avoids using a loop
   D) It automatically optimizes the algorithm
6. Which of the following methods uses recursion to check if a number is prime?
   A) Simple iterative solution
   B) Sieve of Eratosthenes
   C) Optimization by n/2 iterations
   D) Basic recursion technique
7. How does the Sieve of Eratosthenes algorithm improve the efficiency of prime number checking?
   A) By checking numbers in a random order
   B) By iteratively marking non-prime numbers
   C) By checking numbers up to num
   D) By using recursion to identify prime numbers
8. What is the time complexity of the Sieve of Eratosthenes for finding prime numbers?
   A) O(n)
   B) O(n log log n)
   C) O(√n)
   D) O(n²)
9. Which method is most efficient for finding prime numbers in a large range?
   A) Simple iterative solution
   B) Optimization by break condition
   C) Optimization by √n
   D) Sieve of Eratosthenes
10. Why is space complexity O(n) in the Sieve of Eratosthenes method?
    A) It stores numbers up to num in a boolean array
    B) It uses recursion, which requires space
    C) It stores only prime numbers in an array
    D) It stores all factors of a number

As you deepen your understanding of prime number concepts and C programming techniques, it's important to continue upskilling to stay ahead in programming. Let’s see how upGrad can help you build a stronger foundation in C programming and tackle more advanced topics like algorithm optimization and data structures.

Keep Upskilling with upGrad to Keep Up With Industry Trends

upGrad’s courses provide expert training in C programming, covering essential concepts like loops, recursion, and algorithm optimization. You’ll gain hands-on experience, solve real-world challenges, and sharpen your programming skills.

Below are some relevant upGrad courses to elevate your programming skills and advance your career: 

• Data Structures & Algorithms
• Core Java Basics
• Learn Basic Python Programming
• JavaScript Basics from Scratch
• AI-Powered Full Stack Development Course by IIITB

You can also get personalized career counseling with upGrad to guide your career path, or visit your nearest upGrad center and start hands-on training today! 

Similar Reads:

Explore C Tutorials: From Beginner Concepts to Advanced Techniques
Addition of Two Numbers in C: A Comprehensive Guide to C Programming
String Anagram Program in C
C Program to check Armstrong Number
Factorial Program of a Number in C
Fibonacci Series Program in C Using Recursion

Conclusion 

In this blog, we explored various methods to implement a C program for prime numbers, including basic divisibility checks, the Sieve of Eratosthenes, recursive functions, and trial division methods. Each approach offers different levels of efficiency, making it crucial to choose the right method based on your requirements.

Whether you're checking a single number or generating a list of prime numbers, understanding these techniques will enhance your C programming skills. Keep practicing and experimenting to optimize your C program for prime numbers for better performance and accuracy!

Boost your career with our popular Software Engineering courses, offering hands-on training and expert guidance to turn you into a skilled software developer.

Explore our Popular Software Engineering Courses

Master in-demand Software Development skills like coding, system design, DevOps, and agile methodologies to excel in today’s competitive tech industry.

In-Demand Software Development Skills

Stay informed with our widely-read Software Development articles, covering everything from coding techniques to the latest advancements in software engineering.

Read our Popular Articles related to Software