# Check whether a Number is Prime or Not

Write a program to check whether a number is prime or not. Given an integer, We have to write an efficient to check whether a number is prime or not.

What is Prime Number ?

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

NOTE – Two (2) is the only even prime number.

For example – 3, 5, 7, 13  is a prime number, as it’s divisible by 1 and itself. Similarly, 17, 19 etc. are also prime numbers.

6 is not a prime number as it’s divisible by 1, 2, 3 and 6.

Program to print prime numbers from 1 to n using sieve algorithm

Subscribe Our Tutorials

Print Fibonacci series

Program to implement a stack using an array

## How to Check Whether a Number is Prime or Not

METHOD 1

Run a loop from 2 to n-1 (where n is a number) and check whether a number is perfectly divisible by any other number other than 1 and itself. If it’s divisible by any other number other than 1 and itself then it’s not a prime number.

The time complexity of this approach is O(n).

METHOD 2

This approach is better than the first approach, as we run a loop from 2 to n/2.

METHOD 3

This approach is much better than the method 1 and 2. In this approach, we run a loop from 2 to sqrt(n).

The time complexity of this approach is O(n^(1/2)).

We have discussed three approaches to check whether a number is prime or not. The third approach is the most efficient one, let’s implement it through code.

## PHP Code to Check whether a Number is Prime or Not

Let’s create a method checkPrime (). It takes a number as an argument.