C Program to Check Prime Number

Learn how to write a C program to effectively check whether a number is prime or not with our simple and easy-to-follow tutorial. In this guide, you'll learn to write a C program to find whether a number is prime or not. We will break down each step for easy understanding.

What is a Prime Number?

A prime number is a natural number that can only be divided by 1 and itself as a factor. It means it has no other factors and cannot be divided evenly by other numbers. Prime numbers play a vital role in various applications, including cryptography, coding theory, and other fields, due to their unique properties.

Examples of prime numbers:

2, 3, 5, 7, 11, and 13 are a few prime numbers. These numbers can only be divided evenly by 1 or themselves, so they are prime numbers.

Prime Number Check Program in C

Program:

#include <stdio.h>
#include <math.h>  // Necessary for the sqrt function

int main() {
    int n, i, c = 0;

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

    // Immediate check for numbers less than 2
    if (n <= 1) {
        printf("%d is not a Prime number.\n", n);
        return 0;
    }

    // Logic to check if the number is prime
    // Loop only up to the square root of n to find factors of n
    for (i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            c++;  // Factor found
            break;
        }
    }

    if (c == 0) {
        printf("%d is a Prime number.\n", n);  // If no factors found, n is prime
    } else {
        printf("%d is not a Prime number.\n", n);  // Otherwise, n is not prime
    }

    return 0;
}

Program Output:

Enter any number: 7
7 is a Prime number.

Explanation:

Consider a number n=29.

The program first checks if the number is less than or equal to 1. If so, it is not a prime. Otherwise, it proceeds to the loop.

The loop for(i=2; i<=sqrt(n); i++) is executed until the value of i exceeds the square root of n.

• 1st Iteration:
  i = 2 Here, the program checks if n modulo i equals 0.
  29%2 != 0; thus, c is not incremented and remains 0.
  i is incremented for the next iteration, so i = 3.
• 2nd Iteration:
  i = 3 Here, if n % i == 0, then c would be incremented.
  29%3 != 0; thus, c is not incremented and remains 0.
  i is incremented for the next iteration, so i = 4.
• 3rd Iteration:
  i = 4 Here, if n % i == 0, then c would be incremented.
  29%4 != 0; thus, c is not incremented and remains 0.
  i is incremented for the next iteration, so i = 5.
• 4th Iteration:
  i = 5 Here, if n % i == 0, then c would be incremented.
  29%5 != 0; thus, c is not incremented and remains 0.
  i is incremented for the next iteration, so i = 6.

This pattern continues. However, since the loop only runs up to the square root of n, it will stop after checking i = 5 as the square root of 29 is approximately 5.39.

By the end of the loop, if c is still 0, it means that n was not divisible by any of the checked numbers and is, therefore, prime.

Since c remains 0 throughout the iterations for our chosen n=29, the program concludes that n=29 is a prime number.

Conclusion

This tutorial has shown you how to write a C program to check whether a number is prime or not effectively. This prime number code in C is efficient and easy to understand, and it can be used to check for prime numbers of any size.