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 ~ 106 but if the input is greater than 109 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)