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 because a number ‘n’ can have maximum number of factors. So, we can say the most optimized complexity is O().
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.