C Program to Check Whether a Number is Prime or Not

  • Write a C program to check whether a number is prime or not
  • Algorithm check prime number.

A Prime number is a natural number greater than 1 that is only divisible by either 1 or itself. All numbers other than prime numbers are known as composite numbers. Any non-prime number can be expressed as a factor of prime numbers. There are infinitely many prime numbers, here is the list of first few prime numbers
2 3 5 7 11 13 17 19 23 29 31 37....

C program to check a number is prime or not

In this program, we will use brute force approach by testing whether n is a multiple of any integer between 2 and N/2. This is the most basic method of checking the primality of a given integer n is called trial division.

/* 
* C program to check whether a number is prime number or not
*/

#include<stdio.h>
#include<conio.h>

int main() {
  int num, i, isPrime=0;
  printf("Enter a positive number\n");
  scanf("%d",&num);
  /* Check whether num is divisible by any number between 2 to (num/2)
  */
  for(i = 2; i <=(num/2); ++i) {
      if(num%i==0) {
          isPrime=1;
          break;
      }
  }
  
  if(isPrime==0)
      printf("%d is a Prime Number",num);
  else
      printf("%d is NOT a Prime Number",num);
      
  getch();
  return 0;
}
Program Output
Enter a positive number
23
23 is a Prime Number
Enter a positive number
30
30 is NOT a Prime Number

Below program is the optimized version of above program in which we only test with numbers between 2 to sqrt(N). Testing with numbers till N/2 is not required.

/* 
* C program to check whether a number is prime number or not
*/

#include<stdio.h>
#include<conio.h>
#include<math.h>

int main() {
  int num, i, isPrime=0;
  printf("Enter a positive number\n");
  scanf("%d",&num);
  /* Check whether num is divisible by any number between 2 to sqrt(num)
  */
  for(i = 2; i <= (int)sqrt(num); ++i) {
      if(num%i==0) {
          isPrime=1;
          break;
      }
  }
  
  if(isPrime==0)
      printf("%d is a Prime Number",num);
  else
      printf("%d is NOT a Prime Number",num);
      
  getch();
  return 0;
}
Program Output
Enter a positive number
71
71 is a Prime Number
Enter a positive number
45
45 is NOT a Prime Number

C program to find all prime numbers between 1 to N

/*
* C Program to print all Prime numbers between 1 to N
*/
#include<stdio.h>
#include<conio.h>

int main(){

    int num, i, isPrime, n;
    printf("To print all prime numbers between 1 to N\n");
    printf("Enter value of N\n");
    scanf("%d",&num);

    for(n = 1; n <= num; n++){
         isPrime = 0;
         for(i=2;i<=n/2;i++){
             if(n%i==0){
                 isPrime = 1;
                 break;
             }
        }
        
         if(isPrime==0 && n!= 1)
             printf("%d ",n);
    }
   getch();
   return 0;
}
Program Output
To print all prime numbers between 1 to N
Enter value of N
100
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Related Topics
C program to print all prime numbers between 1 to N using for loop
C program to print all prime factors of a number
C program to find sum of prime numbers between 1 to N
C program to check whether a number is magic number
C program to check a number is palindrome or not
C program to check armstrong number
C program to check if two strings are anagram
C program to check string is palindrome
C Program for matrix multiplication
List of all C programs