Find Given Number Is Prime or Not: C

A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

A natural number greater than 1 that is not a prime number is called a composite number. For example, 7 is prime, as only 1 and 7 divide it, whereas 10 is composite, since it has the divisors 2 and 5 in addition to 1 and 10.

In this video tutorial we show you 3 methods of finding whether the user entered number is a prime number or not.

Since every number is divisible by 1, we start the division(in for loop) from 2.

Note: A number can not be divided(to get a whole number) by another number which is greater than itself.

First Method:
Since every number is divisible by 1, we start the division(in for loop) from 2 till one number less than the user entered value.
Example: If user entered 10. For loop starts from 2 to 9.
for(i=2; i<10; i++) or for(i=2; i< =9; i++)

But the draw back: If user enters 500, the loop must get executed from 2 till 499. i.e., 497 times.

Second Method:
Here we reduce the number of iterations in for loop.
i.e., we divide the user entered value by 2 and divide the user entered value from 2 till num / 2;
Example: If user entered 500, we start the division from 2 till 500/2 i.e., till 250 times.

Third Method:
Here we still reduce the number of iterations in the for loop.
i.e., we take the square root of the user entered number and divide the user entered number from 2 till square root of number.
Example: If user entered 500, we start the division from 2 till sqrt(500) i.e., till 22 times.

So this third method is most optimum, as it involves least number of looping.

Video Tutorial: Find Given Number Is Prime or Not: C

Full Free Source Code:

#include < stdio .h >
#include < conio .h >
#include < math .h >
 
void main()
{
int num, i, fact, inum;
clrscr();
 
printf("Enter a number\n");
scanf("%d", &num);
 
inum = sqrt(num);
 
for(i=2; i <= inum ; i++)
 if( num % i == 0 )
 {
   fact = 0;
   break;
 }
 else
   fact = 1;
 
if(fact)
 printf("%d is Prime\n", num);
else
 printf("%d is NOT prime\n", num);
 
getch();
}

Table of all prime numbers up to 1,000: