**Problem Statement:** Given a number N, Check if the number is Prime or not.

**Examples:**

Example 1:Input:N = 7Output:Prime Number.Input:N = 8Output:Not Prime.

** Disclaimer**:

*Don’t jump directly to the solution, try it out yourself first.*

**What is a Prime Number?**

A natural number is called a prime number if it is divisible only by 1 and itself. **Example:** 1, 2, 3, 5, 7, …

Can you think of a naive solution now?

Yes, we simply need to check if the given number is divisible by any number between 2 and N – 1, if yes then it is not prime otherwise it is a prime number.

**Approach:**

- We will run a loop from 2 to 1 number less than the given number, N.
- Now we will check if the given number is divisible by any number in that range.
- If it gets divided by any number then it is not a prime number else it is a prime number.

**Code:**

## C Program

```
#include <stdio.h>
#include<math.h>
int prime(int n){
for(int i=2;i<n;i++)
{
if(n%i==0)
return 0;
}
return 1;
}
int main() {
int n=7;
if(prime(n))
printf("It is a prime number");
else
printf("It is not a prime number");
return 0;
}
```

**Output:** It is a prime number

**Time Complexity:** O(n)

**Space Complexity:** O(1)

**Can we optimise the above approach? **

Yes, we can to some extent. Before that let me ask you a few questions:

- Can 10 be ever divided by a number greater than 5?
- Can 15 be ever divided by a number greater than 7?
- Can 18 be ever divided by a number greater than 9?

No, right?

So you can’t divide a number(N) completely by any number greater than (N/2). Therefore, we don’t need to check for every number from 2 to N-1, we just need to check for every number from 2 to (N/2).

## C Program

```
#include <stdio.h>
#include<math.h>
int prime(int n){
for(int i=2;i<n/2;i++)
{
if(n%i==0)
return 0;
}
return 1;
}
int main() {
int n=7;
if(prime(n))
printf("It is a prime number");
else
printf("It is not a prime number");
return 0;
}
```

**Output:** It is a prime number

**Time Complexity:** O(n)

**Space Complexity:** O(1)

**Is there any library function to check prime numbers in C? **

No, there is no builtin function in C to check for prime.

Special thanks toplease check out this articlefor contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam,Subhrajit Das