FOR FREE MATERIALS
Composite Number
Back to ProgrammingDescription
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.
Code
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 because a number ‘n’ can have maximum number of factors. So, we can say the most optimized complexity is O().
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.
