*Advertisement:*

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.

YouTube Link: http://www.youtube.com/watch?v=3MYx9PrpXEg [Watch the Video In Full Screen.]

**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:**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | #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:**