In this C program, we will check whether a number is prime number or not. 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.

#include<stdio.h> int main() { int num, i, isPrime=0; printf("Enter a positive number\n"); scanf("%d",&num); 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); return 0; }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.

#include<stdio.h> #include<math.h> int main() { int num, i, isPrime=0; printf("Enter a positive number\n"); scanf("%d",&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); return 0; }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

#include<stdio.h> int main(){ int num, i, isPrime, 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); } return 0; }Output

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**