Skip to main content

ProwessApps

Learn · Practice · Excel
About Contact
Login / Register

C Program to check the given number is prime or not

C Code Example — Loop Programs

ADVERTISEMENT

C Program to check the given number is prime or not

Objective

Write a C program to check whether a given number is Prime or not.

Algorithm / Approach

  1. Read a number n from the user.
  2. Initialize a flag variable flag = 1 (assuming the number is prime).
  3. Loop from i = 2 up to the square root of n (sqrt(n)).
  4. Inside the loop, check if n is perfectly divisible by i (n % i == 0).
  5. If it is divisible, set flag = 0 and use break to exit the loop early.
  6. After the loop, if flag == 1, print Prime; else print Not Prime.
main.c 
#include<stdio.h>
#include<math.h>
int main( ) {
 int i, n, flag=1;
 printf("Enter Value of N: ");
 scanf("%d", &n);
 for(i=2; i<=sqrt(n); i++) {
  if(n%i == 0) {
    flag = 0;
    break;
   }
  }
  if(flag == 1) { 
  printf("%d is PRIME NO.\n",n);
  }
  else {
   printf("%d is NOT PRIME NO.\n",n);
  }
 return 0;
}

Expected Output

Enter Value of N: 17
17 is PRIME NO.
Enter Value of N: 9
9 is NOT PRIME NO.

Explanation of the Program

  • A Prime number is a number greater than 1 that is only divisible by 1 and itself (e.g., 2, 3, 5, 7, 11).
  • The most efficient way to check for primality is to loop up to the square root of the number. If a number is divisible by a larger number, that larger number would correspond to a smaller factor that we already checked!
  • The break statement is an optimization. As soon as we find a single divisor, we know the number is NOT prime. There is no need to keep checking the rest of the numbers, so we break out of the loop immediately.

Complexity

Time Complexity O(√n) - Loop runs up to the square root of n.
Space Complexity O(1)
ADVERTISEMENT