# Program to Check Prime Number in C language

**Table of Contents:**

- 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 [â€¦]