Program to Check Prime Number in C language
- Program Introduction:
- Checking Prime number in C Program Explanation / Algorithm:
- Method 1: Detect prime number by checking for factors from 2 to n-1 numbers:
- Method 1: Check or Detect prime number in C program:
- Program Output:
- Method 2: Detect the prime number in C by checking for factors from 2 to n/2 numbers:
- Method 2: Check or Detect prime number program:
- Program Output:
- Method 3: Detect prime number by checking for factors from 2 to Square root of n (sqrt(n)) numbers:
- Method 3: Check prime number in C using Square root (Sqrt) program:
- Program Output:
- Conclusion:
- Related Math Programs:
- References:
Program Introduction:
The Program to Check prime number in c Language. The program should check or detect whether the given number is a prime number or not a prime number.
Here are a couple of examples.
Example 1:
Input:
Enter a Number : 29
Output:
29 is Prime Number
Example 2:
Input:
Enter a Number : 10
Output:
10 is not a Prime Number
Checking Prime number in C Program Explanation / Algorithm:
Any positive number which is divisible by 1 (one) and itself is called Prime Number.
Let’s take ‘n’ as a input number.
So the main idea is to divide the given number by all numbers from 2 to n-1and see if the number is perfectly divisible by any of the numbers between 2 to n-1.
Perfectly divisible means, We should get zero as the remainder after the division. Here is an example.
Example : 10/2 ( Which gives us zero (0) as the remainder )
If a number(2) which perfectly divides any other number(10) then we call that number(2) a factor of 10. So In the above example, 2 is a factor of 10.
Prime Number is such a number, It’s factors are only one (1)and the number itself. It won’t have any other factors.
If the Given Number is perfectly divisible by at least one number from 2to n-1. In other words, if a given number has any factor between 2 to n-1, Then the given number is not a Prime number.
If the Given Number is not divisible(perfectly) by any number between 2 to n-1. Then It is a Prime Number. As it is only divisible by itself and 1.
There are multiple ways to check whether the given number is prime or not. We are going to discuss three different ways in this program
- Method 1 – By checking for factors of the given number(n) from 2 to n-1.
- Method 2 – By checking for factors of the given number(n) from 2 to n/2.
- Method 3 – By checking for factors of the number(n) from 2 to sqrt(n). This method is the most efficient method to check prime numbers.
Let’s start with method 1.
Method 1: Detect prime number by checking for factors from 2 to n-1 numbers:
In this method, We are going to divide the given number( n) with all numbers from 2to n-1.So if the given number is prime, It should not have any factors from the numbers 2 to n-1.
Here is the logic of the program. We are going to take one variable called counter and initialize it with zero (0). We will go through all numbers from 2to n-1. At each iteration(variable 'i' ), we will check if the given number ( n) is perfectly divisible by variable 'i'. And if it is perfectly divisible then we will increase the counter by 1. We will repeat this process for all iterations.
Finally, we check the value of the counter. If the counter value is greater than Zero(0) then The given number ( n) has factor(s). So The number( n) is not a prime number.
If the counter value is equal to zero(0). Then Number( n) is a Prime Number.
Method 1: Check or Detect prime number in C program:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include<stdio.h> int main() {     int n,i;      // Counter variable to count the number of factors     int counter=0;         // Take input number from user     printf("Enter a positive Number : ");     scanf("%d",&n);       // Iterate through 2 to n-1     // At each Iteration check if the 'i' is factor of 'n'     // If 'i' is factor then increase the counter by 1     for(i=2;i<n;i++)     {         // Check if 'i' is factor of 'n'         if(n%i == 0)         {             // 'i' is factor, Increment 'counter' variable             counter++;          }     }      // Check the number of factors of 'n'     // The number of factors stored in 'counter' variable     // If the counter is '0'. Then Number(n) is prime number     if(counter == 0)     {         printf("%d is a Prime Number \n", n);     }     else     {         printf("%d is not a Prime Number \n", n);     }      return 0; } |
Program Output:
We are using the GCC compiler to compile the code.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Compile program with gcc compiler venkey@venkey$ gcc check-prime-method1.c  // Run the executable 'a.out' venkey@venkey$ ./a.out Enter a positive Number : 29 29 is a Prime Number  // Example 2 venkey@venkey$ ./a.out Enter a positive Number : 7 7 is a Prime Number  // Example 3 venkey@venkey$ ./a.out Enter a positive Number : 33 33 is not a Prime Number  // Example 4 venkey@venkey$ ./a.out Enter a positive Number : 4 4 is not a Prime Number venkey@venkey$ |
In the above program, We are unnecessarily looping till the n-1. Which can slow down the execution. So try to improve the above program.
Method 1 (Modified for improving the Performance):
We can slightly modify the above program to improve the performance. In the above program, We are not stopping the loop once we found the factor. The prime number should not have any factors. So we can stop the for loop once we found the first factor Instead of iterating through all the numbers ( 2to n-1).
📢 Stop the Loop once we found the first Factor of ‘n’. Because prime number don’t have any factors from 2 to n-1.
Let’s re-write above program to stop once we found the factor.
Modified Method 1: Check Prime Number in C Language:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include<stdio.h> int main() {     int n,i;      // Counter variable to count the number of factors     int counter=0;         // Take input number from user     printf("Enter a positive Number : ");     scanf("%d",&n);       // Iterate through 2 to n-1     // At each Iteration check if the 'i' is factor of 'n'     // If 'i' is factor then increase the counter by 1     for(i=2;i<n;i++)     {         // Check if 'i' is factor of 'n'         if(n%i == 0)         {             // 'i' is factor, Increment 'counter' variable             // We found one factor of 'n'. Means 'n' is not a Prime             // Break out of the loop             counter++;             break;         }     }      // Check the number of factors of 'n'     // The number of factors stored in 'counter' variable     // If the counter is '0'. Then Number(n) is prime number     if(counter == 0)     {         printf("%d is a Prime Number \n", n);     }     else     {         printf("%d is not a Prime Number \n", n);     }      return 0; } |
Program Output:
|
1 2 3 4 5 6 7 8 9 10 11 |
venkey@venkey$ gcc check-prime-method1-modified.c venkey@venkey$ ./a.out Enter a positive Number : 33 33 is not a Prime Number venkey@venkey$ ./a.out Enter a positive Number : 31 31 is a Prime Number venkey@venkey$ ./a.out Enter a positive Number : 7 7 is a Prime Number venkey@venkey$ |
Method 2: Detect the prime number in C by checking for factors from 2 to n/2 numbers:
This method is also similar to the above method(modified method 1). But we are not going to check all numbers from 2 to n-1for the factors.
It will be enough to check from 2 to n/2 numbers to find the factors. If we found any factor then the number is not a prime number.
So this method is a little fast compared to the above method.
In this method, We are going to divide the given number( n) with all numbers from 2to n/2.So if the given number is prime, It should not have any factors from the numbers 2 to n/2.
Program logic is the same as the above method. The only change is in the number of iterations. Now In the worst case, We will only loop for 2to n/2 times.
Method 2: Check or Detect prime number program:
The program will try to find the factors of the given number 'n' . We will start from 2 and continue till n/2. And we will stop iterating after finding the first factor.
In the worst case, If we don’t find any factor for a given number, Then we will iterate till n/2 number.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include<stdio.h> int main() {     int n,i;      // Counter variable to count the number of factors     int counter=0;         // Take input number from user     printf("Enter a positive Number : ");     scanf("%d",&n);       // Iterate through 2 to n/2     // At each Iteration check if the 'i' is factor of 'n'     // If 'i' is factor then increase the counter by 1     for(i=2; i<=n/2; i++)     {         // Check if 'i' is factor of 'n'         if(n%i == 0)         {             // 'i' is factor, Increment 'counter' variable             // We found one factor of 'n'. Means 'n' is not a Prime             // Break out of the loop             counter++;             break;         }     }      // Check the number of factors of 'n'     // The number of factors stored in 'counter' variable     // If the counter is '0'. Then Number(n) is prime number     if(counter == 0)     {         printf("%d is a Prime Number \n", n);     }     else     {         printf("%d is not a Prime Number \n", n);     }      return 0; } |
Program Output:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
venkey@venkey$ gcc check-prime-method2.c venkey@venkey$ ./a.out Enter a positive Number : 37 37 is a Prime Number venkey@venkey$ ./a.out Enter a positive Number : 39 39 is not a Prime Number venkey@venkey$ ./a.out Enter a positive Number : 87 87 is not a Prime Number venkey@venkey$ ./a.out Enter a positive Number : 3 3 is a Prime Number venkey@venkey$ |
Method 3: Detect prime number by checking for factors from 2 to Square root of n (sqrt(n)) numbers:
This method is also similar to the above methods. But we are not going to check all numbers from 2 to n-1 or 2 to n/2 for finding the factors.
We are going to check only the numbers from 2 to sqrt(n) numbers only. The sqrt(n) means the square root of the number n.
As we know the square root of n is much smaller than the n or n/2. In the worst case, The number of iterations we take for the sqrt(n) method is very less compared above two methods.
The composite Number rule says, If a number is not a prime number ( i.e Composite Number), It should contain at least one factor in the numbers from 2 to the square root of that number ( sqrt(n)). That means, If any number(n) doesn’t have any factor from 2 to the square root of that number ( Sqrt(n)), Then we call that number( n) as a prime number.
For example. If ‘n’ is 10000, In the worst case (let’s assume we don’t found any factors for 10000)
- Method 1 will take around n iterations. That is 10000 Iterations
- Method 2 will take around n/2 iterations. That is 5000 Iterations.
- Method 3 will take around sqrt(n) iterations. That is only 100 Iterations.
If you see Method 3, Prime number check with Square root is very very efficient for larger values. So whenever possible use the sqrt method.
As you can see this Square root ( sqrt(n)) way of calculating the prime number is the fastest and most efficient way to check the prime number.
let’s convert the above logic into the code.
Method 3: Check prime number in C using Square root (Sqrt) program:
Here we are going to use the c programming languages in-builtSquare root( sqrt() ) Function.
But the Square root function is available under math.h header file. So we need to include the <math.h> header file to our program.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include <stdio.h> #include <math.h> int main() {     int n,i;      // Counter variable to count the number of factors     int counter=0;         // Take input number from user     printf("Enter a positive Number : ");     scanf("%d",&n);       // Iterate through 2 to sqrt(n)     // At each Iteration check if the 'i' is factor of 'n'     // If 'i' is factor then increase the counter by 1     for(i=2; i<=sqrt(n); i++)     {         // Check if 'i' is factor of 'n'         if(n%i == 0)         {             // 'i' is factor, Increment 'counter' variable             // We found one factor of 'n'. Means 'n' is not a Prime             // Break out of the loop             counter++;             break;         }     }      // Check the number of factors of 'n'     // The number of factors stored in 'counter' variable     // If the counter is '0'. Then Number(n) is prime number     if(counter == 0)     {         printf("%d is a Prime Number \n", n);     }     else     {         printf("%d is not a Prime Number \n", n);     }      return 0; } |
Program Output:
As we are using sqrt()function of math.h library. Few compilers might need us to externally provide the library path while compiling the program. So that compiler will look for the function in the provided library which will avoid the linking error.
Here I am including the math library by providing the -lmoption while compiling the program.
We have discussed more about sqrt function in the following article, Please look for more info – Prime Number program in C using sqrt (square root ) Function – SillyCodes
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// We compiled the code with GCC // Also Note we are using compilation flage '-lm' to include math library venkey@venkey$ gcc check-prime-method3.c  -lm venkey@venkey$ ./a.out Enter a positive Number : 76 76 is not a Prime Number venkey@venkey$ ./a.out Enter a positive Number : 71 71 is a Prime Number venkey@venkey$ ./a.out Enter a positive Number : 97 97 is a Prime Number venkey@venkey$ ./a.out Enter a positive Number : 100 100 is not a Prime Number venkey@venkey$ |
Conclusion:
In this article, We have looked at different ways to check if the given number is a prime number or not. The most efficient way is to use the square root method.
Related Math Programs:
- Armstrong Number Program in C Language – SillyCodes
- C Program to find sum of digits of a Number | Sum of Digits program in C – SillyCodes
- C program to print all ASCII characters and ASCII values/numbers – SillyCodes
1 Response
[…] Nutshell, We need to find all Factors of the given number and then check if the factor is a prime number or not. If the factor is a prime number, Then said factor is a prime […]