# Prime Number Program using C

Rushali Patnaik
Last Updated: Feb 10, 2023
EASY

## Introduction

A number n is called a prime number if it is only divisible by 1 and the number itself. Prime numbers are more than the number 1 and have precisely two factors: 1 and the number itself.

To check whether a number n is prime or not, we will have to divide n by each number from 2 to n-1. If n is divisible by any number, it is not a prime number, and if no number can divide n, then n is prime. C language provides various looping statements through which our task of checking whether a number is prime or not can be carried out smoothly.

## Code

### Method 1: Loop from 2 to N-1

Time Complexity: O(N)

``````#include<stdio.h>
void main()
{
int i,n=2,is_prime;
is_prime=1;
for(i=2;i<n;i++){
if(n%i==0){
is_prime=0;
break;
}
}
if(is_prime && n>1)
printf("Prime Number\n");
else
printf("Not a Prime Number\n");
}``````

### Output

``Prime  Number``

## Method 2: Loop from 2 to n/2

The loop is taken from 2 to n/2 because no number N has a factor more than N/2.
Time Complexity: O(N/2)

``````#include<stdio.h>
void main() {
int i,n,is_prime;
n=78;
is_prime=1;
for(i=2;i<=n/2;i++){
if(n%i==0){
is_prime=0;
break;
}
}
if(is_prime && n>1)
printf("Prime Number\n");
else
printf("Not a Prime Number\n");
}``````

### Output

``Not a Prime Number``

## Method 3: Loop from 2 to sqrt(n)

The loop is taken from 2 to square root of N because no number N has a factor more than square root of N.
Time Complexity: O(sqrt(N))

Let us understand this approach first. Suppose, n = a*b and a <= b then a*a <= a*b = n, so maximum we should loop over is till a*a <= n i.e. a<=sqrt(n).

``````#include<stdio.h>
void main() {
int i,n,is_prime;
n=7;
is_prime=1;
for(i=2;i*i<=n;i++){
if(n%i==0){
is_prime=0;
break;
}
}
if(is_prime && n>1)
printf("Prime Number\n");
else
printf("Not a Prime Number\n");
}``````

### Output

``Prime Number``

Practice by yourself on online C editor.

## FAQs

1. What is a prime number?
A number n is called a prime number if it is only divisible by 1 and the number itself. Prime numbers are more than the number 1 and have precisely two factors: 1 and the number itself.

2. What is the logic of finding prime numbers using the C language?
To check whether a number n is prime or not, we will have to divide n by each number from 2 to n-1. If n is divisible by any number, it is not a prime number, and if no number can divide n, then n is prime. C language provides various looping statements through which our task of checking whether a number is prime or not can be carried out smoothly.

3. Why is 2 a prime number?
2 is the only even prime number that exists because it has only two factors 1 and itself.

## Key Takeaways

In this blog, we learnt about the various approaches of finding whether a number is prime or not using C language. We hope that this blog has helped you enhance your knowledge, and if you wish to learn more, check out our  Coding Ninjas Blog site and visit our Library. Do upvote our blog to help other ninjas grow.

Happy Learning!