Composite Number

Back to Programming


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