Given a number, we need to check whether it is prime or not in PHP. General approach for prime check is discussed here. In this article we will learn about how to check if a number is prime or not in PHP.
Examples:
Input : 21 Output : Not Prime Input : 31 Output : Prime
Simple Method:
A simple solution is to iterate through all numbers from 2 to n/2 and for every number check if it divides n. If we find any number that divides, we return 0 (false) otherwise we will return 1 (true).
Below is the implementation of this approach in PHP:
PHP
<?php// PHP code to check whether a number is prime or Not// function to check the number is Prime or Notfunction primeCheck($number){ if ($number == 1) return 0; for ($i = 2; $i <= $number/2; $i++){ if ($number % $i == 0) return 0; } return 1;}// Driver Code$number = 31;$flag = primeCheck($number);if ($flag == 1) echo "Prime";else echo "Not Prime"?> |
Output:
Prime
Time Complexity: O(n)
Efficient Method:
We can optimize the above approach by observing that, instead of checking till n, we can check till sqrt(n) because a larger factor of n must be a multiple of smaller factor that has been already checked.
So, we will traverse in the range [2,sqrt(number)] to check if the number is divisible by any number or not. If it is divisible the its not a prime number.
Below is the implementation of this approach in PHP:
PHP
<?php// PHP code to check whether a number is prime or Not// function to check the number is Prime or Notfunction primeCheck($number){ if ($number == 1) return 0; for ($i = 2; $i <= sqrt($number); $i++){ if ($number % $i == 0) return 0; } return 1;}// Driver Code$number = 31;$flag = primeCheck($number);if ($flag == 1) echo "Prime";else echo "Not Prime"?> |
Output:
Prime
Time Complexity: O(sqrt(n))
