## Composite Number

Back to Programming

### Description

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.

### Algorithm

``````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.
``````

# Time Complexity:

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}}$).

# Space Complexity:

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.