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 code to check wether a number is prime or Not ` `// function to check the number is Prime or Not ` `function` `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 code to check wether a number is prime or Not ` `// function to check the number is Prime or Not ` `function` `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))

## leave a comment

## 0 Comments