Find whether a number is prime or not
Algorithm
Input Any integer number (up to 32767) Output Is it a prime number or Not Complexity O(n) Prime(num) 1 Set i=2 2 while i<=num/2 3 if num mod i = 0 4 print "Not a Prime number" and exit; 5 i=i+1 6 if (i==(num/2)+1) 7 Print "Prime number"
Algorithm Description
Step 2 runs only up to num/2 because we know that a number can only be perfectly divisible by maximum to half of itself. Step 3 means if a number is divisible perfectly i.e it is not a prime number If i becomes more than half of a number i.e. no one else less than half of number divides the actual number so it’s a prime number.
C Code
//To find a number is Prime or not?
#include< stdio.h>
#include< conio.h>
int main()
{
int i,num;
printf("Enter a number");
scanf("%d",&num);
i=2;
while(i <=num/2)
{
if(num%i==0)
{
printf("Not a Prime number");
break;
}
i++;
}
if(i==(num/2)+1)
printf("Prime number");
}
