Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Code
2.1.
Method 1: Loop from 2 to N-1 
2.2.
Output
3.
Method 2: Loop from 2 to n/2 
3.1.
Output
4.
Method 3: Loop from 2 to sqrt(n) 
4.1.
Output
5.
FAQs
6.
Key Takeaways
Last Updated: Mar 27, 2024
Easy

Prime Number Program using C

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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. 

Also see: C Static Function, and Tribonacci Series

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

You can also read about dynamic array in c, Strong number in c and Short int in C Programming

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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.

Must Read what is storage class in c

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.

Also read reverse a number.

Happy Learning! 

Previous article
Natural Numbers Program using C
Next article
Factorial using Recursion in C
Live masterclass