Prime Number Algorithm

Algorithm

1. Input   Any integer number (up to 32767)  
2. Output  Is it a prime number or Not  
3. Complexity O(n)  
4. Prime(num)  
5. 1 Set i=2  
6. 2 while i<=num/2  
7. 3      if  num mod i = 0  
8. 4          print "Not a Prime number" and exit;  
9. 5     i=i+1  
10. 6 if (i==(num/2)+1)  
11. 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