In this article, we will write a C program to check whether a given number is a prime number or not. The program takes a number N from the user as input and applies the logic to check whether it is prime or not and shows the output to the user.
Sample Example:
Input: Enter a number: 123
Output: 123 is not a Prime Number.
Explanation: Because 123 is divisible by 3, therefore it's not a prime number
Input: Enter a number: 31
Output: 31 is a Prime Number.
Explanation: Becase 31 is divisible only by 1 and itself, therefore it's a prime numberTo check whether the given number is prime or not, first, let’s first understand what a prime number is.
A prime number is a natural number which is greater than 1 and has only two divisors which are 1 and the number itself. In simple words, a number which is divisible by only 1 and itself is known as a prime number.
For example: 2, 3, 5, 7, 11, 13, 17, . . . etc. are all prime numbers because these numbers are either divisible by 1 or itself.
Note: 2 is the smallest prime number.
So, if we want to find out whether a given number is prime or not, we will have to simply check if the number is divisible by any number other than 1 and the number itself. If yes, it will not be considered a prime number.
From a programming perspective, to determine whether a number is prime or not, we will ask the user to enter a number. After taking the number from user, we will iterate from 2 to half of the number to check if any division is possible. If division is possible that means the number is not a prime number, otherwise it is a prime number.
Following is the code in C Language to check whether a given number is prime or not.
// C program to check whether a number is Prime or not
#include<stdio.h>
int main()
{
// Declare the variables
int n, isPrime = 1;
//Ask user to enter a number
printf("Enter a number: ");
//Store the input into variable n
scanf("%d", &n);
// Iterate to check the number is divisible
// by any other number except 1 and itself
for(int i = 2; i < n; i++){
if(n % i == 0){
isPrime = 0;
break; // Because number is divisible
// no need to check further
}
}
//Check if isPrime is 1 or 0
if(isPrime == 1){
printf("%d is a Prime number.", n);
}
else{
printf("%d is not a Prime number.", n);
}
return 0;
}
Output1:
Enter a number:100 100 is not a Prime number.
Output2:
Enter a number: 17 17 is a Prime number.
Program Explanation:
The program starts by declaring two variables n and isPrime of integer type. It then asks the user to enter a number which is stored in the variable n.
We used printf() to display the message asking the user to enter an integer, and scanf() to get the input and store it in the variable n.
After taking the input from the user, we used a for loop which iterates from 2 to n -1 and checks if the number is divisible by any of the numbers between 2 and n.
If the number is divisible by any of the numbers between the given condition, then we change the value of the variable isPrime to 0 (Initially it is 1) which indicates that the number is not a prime number and breaks the loop instantly.
After getting out of the loop we check the condition that isPrime is storing either 1 or 0. If it has 1 then, we print that the “number is a prime number” otherwise print that “number is not a prime number”.
Method 2: Optimizing the Solution by N/2 Iterations
In the last example, the for loop runs from 2 to n(excluding). It means that in worst cases the loop will run exactly (n-2) times.
We can optimize this solution by running the loop from 2 to n/2(including). The reason behind this optimization is that if a number ‘n’ is not prime, one of its divisors must be less than or equal to n/2.
For example, If we take a non-prime number 48, its divisors will be 1, 2, 3, 4, 6, 8, 12, 16, 24, and 48. If we ignore the number itself from the divisors list, you will notice that the highest divisor is 24 which is half(n/2) of the number itself. That’s the logic we can use to optimize our solution.
See implementation in the following C program:
// C program to check whether a number is Prime or not
#include<stdio.h>
int main()
{
// Declare the variables
int n, isPrime = 1;
//Ask user to enter a number
printf("Enter a number: ");
//Store the input into variable n
scanf("%d", &n);
// Run the loop up to n/2(highest divisor possible)
for(int i = 2; i <= n/2; i++){
if(n % i == 0){
isPrime = 0;
break; // Because number is divisible
// no need to check further
}
}
//Check if isPrime is 1 or 0
if(isPrime == 1){
printf("%d is a Prime number.", n);
}
else{
printf("%d is not a Prime number.", n);
}
return 0;
}
Output:
Enter a number: 37 37 is a Prime number.
Method 3: Optimizing the Solution by √N Iterations
We can further optimize our solution by running the for loop up to √n. The theory behind this optimization is based on the properties of prime numbers and their divisors.
When you find a divisor ‘a’ of a number ‘n’, there’s always a corresponding divisor ‘b’ such that ‘a * b = n’. If ‘a’ is less than or equal to the square root of ‘n’, then ‘b’ must be greater than or equal to the square root of ‘n’ to satisfy the equation.
So, instead of running the loop up to n/2, we can instead run it up to the square root of n i.e. √n.
Note: To find the square root of a number in C, you can use the sqrt() function provided by the <math.h> header library.
See implementation in the following C program:
// C program to check whether a number is Prime or not
#include<stdio.h>
#include <math.h>
int main()
{
// Declare the variables
int n, isPrime = 1;
//Ask user to enter a number
printf("Enter a number: ");
//Store the input into variable n
scanf("%d", &n);
// Run the loop up to square root of n
for(int i = 2; i <= sqrt(n); i++){
if(n % i == 0){
isPrime = 0;
break; // Because number is divisible
// no need to check further
}
}
//Check if isPrime is 1 or 0
if(isPrime == 1){
printf("%d is a Prime number.", n);
}
else{
printf("%d is not a Prime number.", n);
}
return 0;
}
Output:
Enter a number: 47 47 is a Prime number. Enter a number: 50 50 is not a Prime number.
Time Complexity: The time complexity of this approach is O(√N), where N is the number which we want to check.
As the time complexity of this program is lower than the other approaches, we recommend using this approach.
I hope you will find this article helpful. Thanks for reading!
