A number is said to be the perfect number if the sum of its proper divisors (not including the number itself) is equal to the number.
To get a better idea let’s consider an example, proper divisors of 6 are 1, 2, 3. Now the sum of these divisors is equal to 6 (1+2+3=6), so 6 is said to be a perfect number. Whereas if we consider another number like 12, proper divisors of 12 are 1, 2, 3, 4, 6. Now the sum of these divisors is not equal to 12, so 12 is not a perfect number.
Programming in Python is relatively simpler and more fun when compared to other languages because of its simpler syntax, good readability. Now that we are clear with the concept of perfect number let’s write a python program to check if a number is a perfect number or not. Let’s build a python code for checking if the given user input is a perfect number or not and explore the fun in coding with python. Have a look at our data science programs if you are interested to gain expertise.
Read: Python Pattern Programs
Table of Contents
A basic solution for finding a perfect number is to loop over 2 to number-1, maintain the sum of its proper divisors, and check if the sum is equal to the number.
|n=int(input(“enter the number”))|
for i in range(2,n):
print(n,”is a perfect number”)
print(n,”is not a perfect number”)
Let’s walk through the code.
We are first initializing n with the user input and typecasting it to an integer because by default the user input is read as a string in python. We need to check whether n is a perfect number or not. Note that we are initializing the sum with 1 because 1 is a proper divisor for all integers (excluding zero), so that we can exclude an iteration in the loop and directly start from 2.
We are looping over 2 to number-1 and adding the integers to sum if it is a proper divisor. And finally, when we come out of the loop we are checking if the sum obtained is equal to the number or not. Piece of cake right?
Little Optimized Version
After having a dry run over the above program, we may have a question can we optimize it? Well, but we can reduce the number of iterations to number/2 without changing the algorithm. Because we got the idea that a number cannot have a proper divisor greater than number/2.
|n=int(input(“enter the number”))|
for i in range(2,n//2+1):
print(n,”is a perfect number”)
print(n, “is not a perfect number”)
The above snippet is almost similar to the previous one, with the only difference of looping till number/2. Note that we are performing an integer division to avoid converting it to a float type, and we are looping till n//2+1 because the last integer in the range is not considered in the python loop.
When we are asked to find perfect numbers in a given range then our solution would consume time proportional to number^2 i.e., O(n²) time complexity. Because we need to loop over each number in the given range and then check for proper divisors for each number. And few numbers satisfy the perfect number condition. For example, the number of perfect numbers in the range of 0 to 1000 is just 3 (6, 28, 496).
There is an optimized solution for this where we need not loop over all elements to find proper divisors, Euclid’s formula states that 2n−1(2n − 1) is an even perfect number where both n, (2n − 1) is prime numbers. For example, 6 satisfies the above equation with n as 2 and both 2, 22 − 1 (22 − 1 = 3) are prime numbers. But we cannot answer if we were asked to find if there are any odd perfect numbers.
Also, we know that every language has a limit to the range of integers that it can store. With this limitation, we may not have a way to find the largest perfect number.
All these limitations are faced if our input number is big, but if our input number is small then our initial solution would work in less time.
Also Read: Python Framework for Web Development
We’ve known the definition and understood the concept behind the perfect number. Walked through a basic solution for finding a number is a perfect number or not. And after watching the initial solution we’ve optimized it a little bit by reducing the number of iterations. We’ve come through the limitations of our algorithm and discussed Euclid’s formula for finding the even perfect number.
Now that you are aware of the python program to check if a number is a perfect number or not. Try writing the code on your own and try optimizing it if found any overlapping iterations. Also, try building the code for finding perfect numbers in the given range of numbers.
If you are curious to learn about python, data science, check out IIIT-B & upGrad’s Executive PG Programme in Data Science which is created for working professionals and offers 10+ case studies & projects, practical hands-on workshops, mentorship with industry experts, 1-on-1 with industry mentors, 400+ hours of learning and job assistance with top firms.
Explain the complexities of the Perfect Number Program In Python.
A number is said to be a perfect number if it is equal to the sum of its divisors. To check if a number is perfect or not, we have two approaches. The first approach is a naive approach where the time complexity is O(n2) since we are iterating “j” times for each “i” and checking for its divisors.
The second approach is the optimized solution where the time complexity is O(√n). Here we do not need to iterate over every number. We can directly conclude it using Euclid’s formula that is:
2n−1(2n − 1), where n and 2n are prime numbers.
However, this formula does not work for the odd perfect numbers and hence, we have to find another approach for them.
What are the limitations of the approaches of the Perfect Number Program?
Both of these approaches are good but only to some extent. Neither of them can be considered as the perfect approach due to some technicalities. The limitations of these approaches are as follows:
1. The first and the naive approach is worse because it consumes a lot of time and memory and has a time complexity of O(n2). This is because we are using a nested loop and iterating the inner loop n times for every element of the outer loop. This approach is naive and will give TLE for larger values of n and hence is not recommended.
2. Then we have an optimized approach that solves the problem in O(√n). This is a good approach unless the odd perfect numbers come into play. We can not check for the odd perfect numbers with this approach as it is based on “Euclid’s formula for even perfect numbers” that only works for even perfect numbers.
Is Python suitable for competitive programming?
Python evolved from C/C++ and even Java and is considered to be the best-suited language for research and development purposes. But when it comes to competitive programming, a majority of the programming community avoids Python. The reason being Python is the slowest among these three languages.