Thursday, 4 January 2018

Check If a number is prime or not | PHP

Tags

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.




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