A number is said to be **a composite number** if **the number has one or more factors excluding 1 and the number itself**.

**For example**, **let the number be 10**, **the factors of 10 **are** 2 and 5 excluding 1 and itself**. Therefore, 10 is a composite number.

Similarly, **if the number be 7**, then **it has no factor except 1 and itself**. Therefore**, it is not a composite number**.

For this program, a number is taken as input and then the number of factors of this number is counted starting from 2 to half of the number. If **the number of factors is more than 0**, then the number is a composite number, otherwise not.

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

Here for simplicity, the number is divided by the numbers from 1 to the number to check whether **the number is a composite number or not** so, the **time complexity is O****(n)**.

But for **more optimization**,** we can check** from **2 to **$\sqrt{\mathrm{n}}$** **because **a number ‘n’ can have maximum **$\sqrt{\mathrm{n}}$** 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 check whether a number is a composite number or not.