# Prime Number Program in C

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

Examples:

```Example 1:
Input: N = 7
Output: Prime Number.

Input: N = 8
Output: Not Prime.```

DisclaimerDon’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.