C Program to Check if a Number is Prime

Write a program in c to check if a number is prime or not.

For example,

Input
7
Output
7 is prime

Input
14
Output
14 is not prime

Prime Number: A positive number that is divisible by exactly 2 numbers – by 1 and by itself. For example, 13. 13 is only divisible by 1 and 13. Thus, 13 is prime.
Note: 1 is not a prime number because it is divisible by only 1 number that is 1.

Naive Approach

Let N be the input number. The simplest way to check if N is prime or not is to traverse all the numbers in the range [2, N-1] and check if any of them divides N. If any number do divide N, then it means N is divisible by more than 2 numbers. Thus, N is not a prime.

#include<stdio.h>

int main() {
	int i,flag;
	int n; // input
	
	printf("Enter to number to check if it is prime or not: ");
	scanf("%d",&n);
	
	if(n==1){
		printf("%d is prime",n);
	}
	else{
		
		flag = 0;
		for(i = 2;i<=n-1;++i){
			if(n%i==0){
				// this segment of code runs if
				// n is divisible by i
				// thus n is not prime
				// we set flag to 1 and break the loop
				flag=1;
				break;
			}
		}
		
		if(flag==1)
			printf("%d is not prime",n);
		else
			printf("%d is prime",n);
		
	}	
}

Output

Enter to number to check if it is prime or not: 45
45 is not prime

Efficient Approach

In the above code, the loop ranges from 2 to N-1 but it’s unnecessary. No divisor of N can be greater than N/2. The only number greater than N/2 that can divide N is N itself.

Therefore, we change the loop range from [2, N-1] to [2, N/2].

#include<stdio.h>

int main() {
	int i,flag;
	int n; // input
	
	printf("Enter to number to check if it is prime or not: ");
	scanf("%d",&n);
	
	if(n==1){
		printf("%d is prime",n);
	}
	else{
		
		flag = 0;
		for(i = 2;i<=n/2;++i){
			if(n%i==0){
				flag=1;
				break;
			}
		}
		
		if(flag==1)
			printf("%d is not prime",n);
		else
			printf("%d is prime",n);
		
	}	
}

Output

Enter to number to check if it is prime or not: 29
29 is prime

More Efficient Approach

The above 2 code works fine if the input is small N ~ 10⁶ but if the input is greater than 10⁹ then performance may suffer.

We can optimize the code further. Instead of looking for divisor in the range [2, N/2], we can change the range to [2, SquareRoot(N)].

Let X be the square root of N. Then

All divisors of N should be in form

Both p and q cannot be greater than X, it will result in p*q > N. Similarly, both p and q cannot be smaller than X, it will result in p*q < N.

Therefore, we can say that . In simple words, if a number is a divisor of N then there exists another number that is also a divisor of N. Thus, we don’t have to loop beyond X to check if a number divides N or not.

#include<stdio.h>
#include<math.h>
int main() {
	int i,flag;
	int n; // input
	
	printf("Enter to number to check if it is prime or not: ");
	scanf("%d",&n);
	
	if(n==1){
		printf("%d is prime",n);
	}
	else{
		
		flag = 0;
		for(i = 2;i<=sqrt(n);++i){
			if(n%i==0){
				flag=1;
				break;
			}
		}
		
		if(flag==1)
			printf("%d is not prime",n);
		else
			printf("%d is prime",n);
		
	}	
}

Output

Enter to number to check if it is prime or not: 1231
1231 is prime

Read
Right Shift Array by One
Find all Subset of Array in C++
Reverse a string in C without string functions (using both loop and recursion)