A number is called a **prime number** if the number is **only divisible by 1 and itself**. The prime numbers have** exactly two factors- 1** and **the number itself**.

For **example number 5**.

5 is only divisible by 1 and 5. The number of factors of 5 is 2. So, **5 is a prime number**.

If **the number is 4**, it is divisible by 1, 2 and 4. So, instead of 1 and 4, it has another factor 2. The number of factors of 4 is 3. So, it is **not a prime number**.

So, the main logic of the program is to take the number as input and the number of factors are counted. If the number of factor is 2 then it is a prime number otherwise it is not a prime number.

```
INPUT: A number.
OUTPUT: Whether it is a prime number or not.
PROCESS:
Step 1: [Taking the input]
Read n [the number which is to be checked]
Step 2: [Checking for the prime number]
Set c<-0
For i=1 to n repeat
If n mod i=0 then
Set c<-c+1
[End of ‘if’]
[End of ‘for’ loop]
If c=2 then
Print "Prime Number"
Else
Print "Not a prime number"
[End of ‘if’]
Step 3: Stop.
```

Here for this program the **time complexity to check whether a number is a prime number or not** is **O(n)** where **n is the given input**. For the simplicity of the program the loop has been written from 1 to n to check for a prime number.

But for more optimization **we can check from 2 to **$\sqrt{\mathrm{n}}$ because a **number ‘n’ can have **a **maximum number of factors**. So, we can say the **most optimized complexity** is **O(**$\sqrt{\mathrm{n}}$**)**.

The **space complexity of this program** is **O(1)** as it requires a constant number of memory spaces to execute the program.

Contributed by