Prime Number Program in C: Logic, Code, and Examples

Best Prime Number Program in C

The best way to check whether a number is prime in C is to test divisibility only up to the square root of the number, without using a separate function. This is faster than checking every number up to n.

#include <stdio.h>

int main() {
   int n, i, isPrime = 1;

   printf("Enter a number: ");
   scanf("%d", &n);

   if (n <= 1) {
       isPrime = 0;
   } else {
       for (i = 2; i * i <= n; i++) {
           if (n % i == 0) {
               isPrime = 0;
               break;
           }
       }
   }

   if (isPrime) {
       printf("%d is a prime number.\n", n);
   } else {
       printf("%d is not a prime number.\n", n);
   }

   return 0;
}

Sample output:

Enter a number: 29
29 is a prime number.

This program first checks whether the number is less than or equal to 1. If so, the number is not prime. Otherwise, the loop runs from 2 up to sqrt(n) to check whether the number is divisible by any other number. We use the condition i * i <= n to avoid using the sqrt() function directly. This program marks the number as non-prime if it finds any factor and breaks out of the loop. The time complexity of this algorithm is O(sqrt(n)). Since we check the number inline in the main() method, this program also answers your question, "prime number program in C without using a function."

Prime Number Logic in C

Prime number logic in C checks whether a number has any factor other than 1 and itself. The first condition is simple: if the number is less than or equal to 1, it is not prime.

For numbers greater than 1, start dividing the number by every integer from 2 up to sqrt(n). If n % i == 0, then i is a factor of n, so the number is not prime. If the loop completes without finding any such divisor, the number is prime.

Checking only up to sqrt(n) works because factors come in pairs. For example, 36 has factor pairs such as 2 x 18, 3 x 12, 4 x 9, and 6 x 6. Once you cross the square root, the paired factor has already been checked on the smaller side.

Want a Top Software Development Job? Start Here!AI-Powered Full Stack Developer ProgramExplore Program

Algorithm to Check Prime Number in C

1. Read the input number.
2. If the number is less than or equal to 1, mark it as not prime.
3. Run a loop from 2 while i * i <= n.
4. If n % i == 0, mark the number as not prime and stop.
5. If no divisor is found, mark the number as prime.
6. Print the final result.

This algorithm is the cleanest option for beginners because it avoids unnecessary checks while keeping the logic easy to follow.

C Program to Check Prime Number Using For Loop

Here is a simple loop-based C program to check whether a number is prime. It uses a for loop, which is usually the cleanest choice for this problem because the start and end conditions are clear.

#include <stdio.h>

int main() {
   int n, i, flag = 1;

   printf("Enter a number: ");
   scanf("%d", &n);

   if (n <= 1) {
       flag = 0;
   }

   for (i = 2; i * i <= n && flag == 1; i++) {
       if (n % i == 0) {
           flag = 0;
       }
   }

   if (flag == 1) {
       printf("Prime number");
   } else {
       printf("Not a prime number");
   }

   return 0;
}

C Program to Check Prime Number Using While Loop

You can write the same divisibility logic with a while loop instead of a for loop. This is useful when the increment step needs to happen conditionally, or when the loop is part of a larger while-driven program structure.

#include <stdio.h>

int main() {
   int n, i, flag = 1;

   printf("Enter a number: ");
   scanf("%d", &n);

   if (n <= 1) {
       flag = 0;
   }

   i = 2;
   while (i * i <= n && flag == 1) {
       if (n % i == 0) {
           flag = 0;
       }
       i++;
   }

   if (flag == 1) {
       printf("%d is a prime number.\n", n);
   } else {
       printf("%d is not a prime number.\n", n);
   }

   return 0;
}

Sample output:

Enter a number: 17
17 is a prime number.

A for loop and a while loop produce the same result here. The for loop is usually preferred for readability since the initialization, condition, and increment sit in one line. Still, the while loop version is common in interview settings where the loop counter needs to be manipulated inside the body.

Here's How to Land a Top Software Developer JobAI-Powered Full Stack Developer ProgramExplore Program

C Program to Check Prime Number Using Do-While Loop

A do-while loop runs its body at least once before checking the condition, so it needs one extra safeguard. Testing n % i == 0 on the very first pass with i = 2 would wrongly mark 2 itself as not prime, so the program checks for n == 2 separately before entering the loop.

#include <stdio.h>

int main() {
   int n, i, flag = 1;

   printf("Enter a number: ");
   scanf("%d", &n);

   if (n <= 1) {
       flag = 0;
   } else if (n == 2) {
       flag = 1;
   } else {
       i = 2;
       do {
           if (n % i == 0) {
               flag = 0;
           }
           i++;
       } while (i * i <= n && flag == 1);
   }

   if (flag == 1) {
       printf("%d is a prime number.\n", n);
   } else {
       printf("%d is not a prime number.\n", n);
   }

   return 0;
}

Sample output:

Enter a number: 23
23 is a prime number.

This edge case (guarding n == 2 before the loop) is a common source of bugs in do-while prime checkers found elsewhere online, and is worth calling out explicitly for readers who adapt the loop-based version into a do-while version themselves.

C Program to Check Prime Number Using Function

A function-based prime number program is cleaner when you need to reuse the same logic several times. This is useful for checking many numbers, printing prime numbers within a range, or implementing the logic in a larger program.

#include <stdio.h>
#include <stdbool.h>

bool isPrime(int n) {
   int i;

   if (n <= 1) {
       return false;
   }

   for (i = 2; i * i <= n; i++) {
       if (n % i == 0) {
           return false;
       }
   }

   return true;
}

int main() {
   int n;

   printf("Enter a number: ");
   scanf("%d", &n);

   if (isPrime(n)) {
       printf("%d is a prime number.", n);
   } else {
       printf("%d is not a prime number.", n);
   }

   return 0;
}

You can also write this function to return 1 for a prime and 0 for a non-prime. Using bool simply makes the result easier to understand.

Dive Deep Into Java Core ConceptsJava Certification TrainingENROLL NOW

C Program to Check Prime Number Using Recursion

A recursive version replaces the loop with a helper function that calls itself with the next candidate divisor. The base cases stop the recursion once it finds a factor or the divisor exceeds sqrt(n).

#include <stdio.h>

int checkPrime(int n, int i) {
   if (i * i > n) {
       return 1;
   }
   if (n % i == 0) {
       return 0;
   }
   return checkPrime(n, i + 1);
}

int isPrime(int n) {
   if (n <= 1) {
       return 0;
   }
   return checkPrime(n, 2);
}

int main() {
   int n;

   printf("Enter a number: ");
   scanf("%d", &n);

   if (isPrime(n)) {
       printf("%d is a prime number.\n", n);
   } else {
       printf("%d is not a prime number.\n", n);
   }

   return 0;
}

Sample output:

Enter a number: 13
13 is a prime number.

The recursive version keeps the same O(sqrt(n)) time complexity as the loop-based versions, since it still makes at most sqrt(n) recursive calls. Recursion is worth showing for interview practice, but for production code, the loop or function version is generally preferred, since deep recursion adds call-stack overhead that the loop versions avoid.

Learn 45+ in-demand full-stack development skills and tools, including Frontend Development, Backend Development, Version Control and Collaboration, Database Management, and AI-Assisted Development, with our Full Stack Developer Course.

C Program to Print Prime Numbers From 1 to n

To print prime numbers from 1 to n, use a reusable isPrime() function and call it for every number in the range. This keeps the program clean and avoids repeating the same divisibility logic.

#include <stdio.h>
#include <stdbool.h>

bool isPrime(int n) {
   int i;

   if (n <= 1) {
       return false;
   }

   for (i = 2; i * i <= n; i++) {
       if (n % i == 0) {
           return false;
       }
   }

   return true;
}

int main() {
   int n, i;

   printf("Enter the value of n: ");
   scanf("%d", &n);

   printf("Prime numbers from 1 to %d are: ", n);

   for (i = 1; i <= n; i++) {
       if (isPrime(i)) {
           printf("%d ", i);
       }
   }

   return 0;
}

Sample output:

Enter the value of n: 20
Prime numbers from 1 to 20 are: 2 3 5 7 11 13 17 19

C Program to Find Prime Numbers in a Range

Printing primes between two arbitrary numbers (not just from 1) needs a start and end value, and is typically written with a nested loop: an outer loop that walks through the range, and an inner loop that checks each number for primality.

#include <stdio.h>

int main() {
   int start, end, i, j, isPrimeNum;

   printf("Enter the range (start end): ");
   scanf("%d %d", &start, &end);

   printf("Prime numbers between %d and %d are: ", start, end);

   for (i = start; i <= end; i++) {
       isPrimeNum = 1;

       if (i <= 1) {
           isPrimeNum = 0;
       }

       for (j = 2; j * j <= i && isPrimeNum == 1; j++) {
           if (i % j == 0) {
               isPrimeNum = 0;
           }
       }

       if (isPrimeNum == 1) {
           printf("%d ", i);
       }
   }

   return 0;
}

Sample output:

Enter the range (start end): 10 30
Prime numbers between 10 and 30 are: 11 13 17 19 23 29

This nested-loop structure is what most C textbooks mean by a "nested loop" prime number program, and it generalizes the 1-to-n version above to any start and end value.

Master Core Java 8 Concepts, Java Servlet, & More!Java Certification TrainingENROLL NOW

C Program to Find the First N Prime Numbers

Finding the first N primes is a different problem from printing primes up to a limit. Here, the loop keeps checking increasing numbers until it has found N primes, regardless of how large the numbers get.

#include <stdio.h>
#include <stdbool.h>

bool isPrime(int n) {
   int i;

   if (n <= 1) {
       return false;
   }

   for (i = 2; i * i <= n; i++) {
       if (n % i == 0) {
           return false;
       }
   }

   return true;
}

int main() {
   int n, count = 0, num = 2;

   printf("Enter the value of N: ");
   scanf("%d", &n);

   printf("First %d prime numbers are: ", n);

   while (count < n) {
       if (isPrime(num)) {
           printf("%d ", num);
           count++;
       }
       num++;
   }

   return 0;
}

Sample output:

Enter the value of N: 10
First 10 prime numbers are: 2 3 5 7 11 13 17 19 23 29

Optimized Prime Number Program in C Using sqrt(n)

The optimized method checks possible divisors only up to sqrt(n). In C, you can write this as i * i <= n, which avoids importing the math library and keeps the code simple.

Checking up to n is slower because it tests many values that yield no new information. Checking up to n/2 is better, but still unnecessary. Checking up to sqrt(n) is the best method for testing a single number because any larger factor must have a smaller matching factor that has already been checked.

Ready to expand your software development skills? Simplilearn’s Java Course helps you learn Java, Java EE, and service-oriented architecture concepts. Explore the course to build practical knowledge and strengthen your foundation for working with enterprise-level software applications.

Sieve of Eratosthenes in C

The Sieve of Eratosthenes is the better method when you need to find many prime numbers, such as all primes from 1 to n. Instead of testing each number separately, it marks multiples of each prime as not prime.

Compact pseudocode:

Create an array isPrime[0..n] and set all values to true
Set isPrime[0] and isPrime[1] to false

For p from 2 while p * p <= n:
   If isPrime[p] is true:
       Mark all multiples of p from p * p to n as false

Print all indexes that are still marked true

The Sieve has a time complexity of O(n log log n) and a space complexity of O(n). It is faster than checking every number one by one when the range is large.

Time Complexity of Prime Number Programs in C

Different prime number programs use different checking limits. The best method depends on whether you are checking a single number or finding many primes within a range.

For a single number, use the sqrt(n) method. For a range or list of many primes, use the Sieve of Eratosthenes.

Common Mistakes in C Programs for Prime Numbers 

1. Counting 1 as prime. Prime numbers must be greater than 1. Reject 0, 1, and negative numbers first.
2. Looping till n. Checking every number up to n is unnecessary. Stop at sqrt(n) for better efficiency.
3. Not breaking the loop. Once you find a divisor, the number is not prime. Break the loop immediately.
4. Missing edge cases—test 0, 1, 2, negative numbers, and large inputs before finalizing the code.
5. Do-while off-by-one on n == 2. A do-while loop starting at i = 2 executes its body before checking the loop condition, so it can wrongly test 2 % 2 == 0 and mark 2 as not prime. Guard n == 2 separately, as shown above.
6. Mixing up program goals. Checking one number, printing primes up to a limit, finding primes in a range, and finding the first N primes all need slightly different logic, even though they share the same core isPrime check.

Wondering how Software Engineers reach senior and leadership roles? Explore the skills, technologies, salary growth, and career progression behind one of the world's most in-demand jobs with this software engineer roadmap.

Conclusion

C programming for prime numbers is an excellent starting point for understanding loops, conditions, divisors, functions, recursion, and optimization. The simplest algorithm for prime numbers is written, and edge cases are considered (e.g., 0, 1, negative integers). An optimized algorithm checks division only up to the square root of an integer. After that, you can tackle more complex tasks, such as finding prime numbers in a specified interval, finding the first N prime numbers, and implementing algorithms using functions or recursion. You can also use the Sieve of Eratosthenes to find prime numbers.

Once you are comfortable with programming fundamentals like loops, functions, algorithms, and problem-solving, the next step is applying those skills to build intelligent AI systems. Simplilearn's Applied Agentic AI program helps you design and develop AI-powered applications, agentic AI systems, and automated workflows through 10 weeks of live, hands-on learning.

Key Takeaways

• A prime number is greater than 1 and has exactly two factors: 1 and itself.
• Prime number programs in C use loops, conditions, divisibility checks, and edge case handling.
• The optimized method checks divisibility only up to sqrt(n), often written as i * i <= n.
• The for, while, do-while, function, and recursive versions share the same core logic, but the do-while version needs an explicit guard for n == 2.
• Function-based programs are useful for checking multiple numbers or printing primes from 1 to n.
• Finding primes in a range (nested loop) and finding the first N primes are related but distinct problems.
• For large ranges, the Sieve of Eratosthenes is more efficient than checking each number individually.

FAQ

1. How do you check if a number is prime in C?

Check whether the number is divisible by any integer from 2 up to sqrt(n). If you find no divisors, the number is prime. In C, this condition is usually written as i * i <= n to avoid using the sqrt() function directly.

2. Why do we check divisors up to the square root for prime numbers?

Factors of a number always come in pairs, and one factor in each pair is always less than or equal to the square root of the number. If no divisor exists up to sqrt(n), no larger divisor can exist either, so checking further is unnecessary.

3. Is 1 a prime number in C?

No. A prime number must have exactly two factors: 1 and itself. The number 1 has only one factor, so it does not meet the definition, and every prime-checking program should explicitly reject it with a condition like n <= 1.

4. What is the time complexity of checking a single prime number?

Checking a single number for primality using the sqrt(n) method runs in O(sqrt(n)) time. A brute-force check up to n or n/2 runs in O(n) time, which is slower for large numbers.

5. How do you find the first N prime numbers in C?

Use a counter and an incrementing candidate number. Keep testing each candidate with an isPrime() function, print it, and increment the counter whenever you find a prime; stop once the counter reaches N.

6. Which prime number program in C is best for interviews?

For interviews, use the optimized sqrt(n) method. Start by rejecting 0, 1, and negative numbers, then check divisibility while i * i <= n. This shows you understand edge cases, loop logic, and basic optimization, and being able to explain the recursive version also signals a stronger grasp of the underlying algorithm.