CREATE OWN LIBRARY
Perfect Number
Back to ProgrammingDescription
A number is said to be a perfect number if the sum of the factors of the number (including 1, excluding itself) returns back the original number.
For example, let the number be 6.
The factors of the number are 1, 2, 3 (including 1, excluding itself)
Therefore, the sum of the factors is 1+2+3=6 which is the same as the original number. So, 6 is a perfect number.
If the number is 16.
Then the factors are: 1, 2, 4, 8 (including 1, excluding itself)
The sum of the factors is 1+2+4+8=15, which is not equal to the original number.
Hence, 16 is not a perfect number.
Here, the factors are found by using a ‘for loop’, and if a factor is found it is added to the sum of the previous factors. After executing the loop, the sum is compared with the original number. If both are the same then it is considered a perfect number, otherwise not.
Algorithm
INPUT: A number to check
OUTPUT: Whether it is a perfect number or not
PROCESS:
Step 1: [Taking the input]
Read n
Step 2: [Checking for perfect number]
Set s<-0
[Loop to find the factors of the number]
For i=1 to n/2 repeat
[Adding the factors]
If n mod i=0 then
Set s<-s+i
[End of ‘if’]
[End of ‘for’ loop]
[Checking for perfect number]
If s=n then
Print "The given number is a perfect number"
Else
Print "The given number is not a perfect number"
[End of ‘if-else’]
Step 3: Stop.
Code
Time complexity:
for(i=1;i<=n/2;i++)-------------------------------------O(n)
{
//adding the factors
if(n%i==0)-------------------------------------O(1)
s=s+i;
}
In this program, the time complexity of checking a perfect number is O(n) where n is the given number.
But for more optimization, we can check from 2 to to check for perfect number 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 memory space to check for a perfect number for any given input.
Contributed by
