Prime Number Program using C

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

You can also read about dynamic array in c.

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!