We will discuss a solution here with time complexity O(sqrt(n)) where n is the number which we have to check whether it is prime or not. In this example, instead of check till n we will check till sqrt(n) because a larger factor of n will be a multiple of smaller factor which is already checked.

Therefore, we will check from (2,sqrt(n)). PHP program along with output is given below.

Therefore, we will check from (2,sqrt(n)). PHP program along with output is given below.

**PROGRAM**<?php function check_prime($number){ if($number==1) { return 0; } for($i=2;$i<=sqrt($number);$i++){ if($number%$i==0) return 0; } return 1; } //Driver code $array=array(33,45,19,67,11); for($i=0;$i<5;$i++){ if(check_prime($array[$i])){ echo $array[$i]." is a prime number"; } else{ echo $array[$i]." is not a prime number"; } } ?>

**OUTPUT:**

EmoticonEmoticon