check whether a given number is prime or not

/* Write a C program to check whether a given number is prime or not *
* and output the given number with suitable message */

#include stdio.h
#include stdlib.h
#include conio.h

void main()
{
int num, j, flag;

clrscr();

printf("Enter a number\n");
scanf("%d", &num);

if ( num <= 1)
{
printf("%d is not a prime numbers\n", num);
exit(1);
}

flag = 0;

for ( j=2; j<= num/2; j++)
{
if( ( num % j ) == 0)
{
flag = 1;
break;
}
}

if(flag == 0)
printf("%d is a prime number\n",num);
else
printf("%d is not a prime number\n", num);
}
/*------------------------
Output
RUN 1
Enter a number
34
34 is not a prime number

RUN 2
Enter a number
29
29 is a prime number
-----------------------------*/

This program checks whether the given number is prime or not. We know that a prime number is not divisible by any natural number other than 1. So if we think a little bit it is the same that if any number till the half of given number is not diving it, It is meant to be a prime. Because if the one factor is greater than half of the given number, then the other factor is less 2, which is not a natural number. Hence it can be termed as prime.

Hence we initialize a variable to 2 and increment it till it reaches half of the given number. If at any time we get a remainder zero, we declare it as not prime, else its accepted as a prime number