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

Best Prime Number Program in C

The best way to check a prime number in C is to test divisibility only up to the square root of the number. 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 it is, the number is not prime. Otherwise, the loop checks divisibility from 2 up to sqrt(n). The condition i * i <= n is a simple C-friendly way to avoid calling sqrt() directly. If any divisor is found, the program marks the number as not prime and stops the loop. The time complexity is O(sqrt(n)).

Prime Number Logic in C

Prime number logic in C is based on checking 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.

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 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;
}

The same logic can also be written using a while loop. However, a for loop is easier to read here because the divisibility check operates over a fixed numeric range.

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.

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

This approach directly answers range-based prime number problems in C.

Unleash Your Career as a Full Stack Developer!AI-Powered Full Stack Developer ProgramEXPLORE COURSE

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.

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.

Advance Your Full Stack Career!AI-Powered Full Stack Developer ProgramEXPLORE COURSE

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 large range, use the Sieve of Eratosthenes.

From C to Java and Beyond! Take your programming skills to the next level with our Java Certification Course. Join Now!

Common Mistakes in Prime Number Programs

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 a divisor is found, 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. Mixing up program goals: Checking one number, printing primes in a range, and summing primes need different logic

Conclusion

A prime number program in C is a simple yet powerful way to learn about loops, conditions, divisibility, functions, and optimization. Start with the basic logic, handle edge cases like 0, 1, and negative numbers, then improve efficiency by checking divisibility only up to sqrt(n). Once this logic is clear, you can easily extend it to print prime numbers in a range, use functions, or apply the Sieve of Eratosthenes for larger inputs.

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
• Function-based programs are useful for checking multiple numbers or printing primes from 1 to n
• For large ranges, the Sieve of Eratosthenes is more efficient than checking each number one by one

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.