Find Given Number Is Prime or Not: C

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.

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


You need to a flashplayer enabled browser to view this YouTube video

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



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:


Leave a Reply

Your email address will not be published. Required fields are marked *