Prime number or Not in C using For Loop

by devang · Published December 19, 2015 · Updated January 1, 2016

Before going to the program for Prime Number or Not first let us understand what is a Prime Number?

Prime Number:

A Prime Number is a number greater than 1 and which is only divisible by 1 and the number itself.

For example,

11 is a Prime Number, because 11 is not divisible by any number other than 1 and 11.

To find whether a Number is Prime Number or Not it is enough to check whether ‘n’ is divisible by any number between 2 and √n. If it is divisible then ‘n’ is not a Prime Number otherwise it is a Prime Number.

Program code for Prime Number or Not in C:


/* Prime Number or Not */
#include<stdio.h>
#include<conio.h>
#include<math.h>

void main()
{
    int n, i, flag=0;
    clrscr();
    
    printf("\n\n  Enter a positive integer value: ");
    scanf("%d",&n);
    
    /* Loop to check whether 'n' is divisible by any number between 2 and sqrt(n) */
    for(i=2;i<=sqrt(n);i++)
    {
        if(n%i==0)
        {
            flag=1;
            break;
        }
    }
    
    /* if else condition to print Prime Number or Not */
    if (flag==0)
    {
        printf("\n  %d is a prime number.",n);
    }
    else
    {
        printf("\n  %d is not a prime number.",n);
    }
    getch();
}

Working:

First the computer reads the positive integer value from the user.
Then using for loop it checks whether ‘n’ is divisible by any number between 2 and √n.
Finally if else condition is used to print the number is prime number or not .

Step by Step working of the above Program Code:

For Prime Number:

Let us assume that a user enters the positive integer value as 13.
It assigns the value of flag=0, n=13.
It assigns the value of i=2 and the loop continues till the condition of the for loop is true.

3.1. i<=sqrt(n) (2<=√13) for loop condition is true

n%i==0 (13%2==0) if condition is false

i++ (i=i+1) So i=3

3.2. i<=sqrt(n) (3<=√13) for loop condition is true

n%i==0 (13%3==0) if condition is false

i++ (i=i+1) So i=4

3.3. i<=sqrt(n) (4<=√13) for loop condition is false

It comes out of the for loop.

flag==0 (0==0) if condition is true

So it prints 13 is a prime number.

Thus program execution is completed.

For Not a Prime Number:

Let us assume that a user enters the positive integer value as 9.
It assigns the value of flag=0, n=9.
It assigns the value of i=2 and the loop continues till the condition of the for loop is true.

3.1. i<=sqrt(n) (2<=√9) for loop condition is true

n%i==0 (9%2==0) if condition is false

i++ (i=i+1) So i=3

3.2. i<=sqrt(n) (3<=√9) for loop condition is true

n%i==0 (9%3==0) if condition is true

It assigns flag=1

breaks the loop and comes out of the for loop