Programs

Perfect Number Program In Python: How to check if a number is perfect or not?

Introduction

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.

The following article will provide you with all the relevant details about how to perform and find the perfect number program in Python. It will also highlight some of the diverse ways in which you can get a perfect square in Python using the perfect number program in Python. Keep reading to learn all about it!

Read: Python Pattern Programs

Python Program

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”))
sum=1
for i in range(2,n):
if(n%i==0):
sum=sum+i
if(sum==n):
print(n,”is a perfect number”)
else:
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”))
sum=1
for i in range(2,n//2+1):
if(n%i==0):
sum=sum+i
if(sum==n):
print(n,”is a perfect number”)
else:
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.

Explore our Popular Data Science Courses

upGrad’s Exclusive Data Science Webinar for you –

Watch our Webinar on How to Build Digital & Data Mindset

 

Limitations

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.

What is Perfect Square In Python?

A perfect square is basically the result you get from multiplying a whole number with itself. For example, 36 is a perfect square because it is the result of 6 times 6. However, 33, is not a perfect square. Simultaneously, squaring number Python is relatively easy, however checking if the value is a perfect square can be a bit time-consuming. There are technically various ways to check whether a number is a perfect square. One among those might include, taking the integer square root of the number, following which you square that value. It is now time for you to compare the result with the original number. If both of them are the same, then you have got a perfect square. This method can also be used for number Python.

Apart from this, there are also two other methods or algorithms that you can use to check for a perfect square in Python. In the first method, you need to take the floor() value square root of the number. Following this, you have to multiply the square root twice. Once you have done that, you can then compare the result of the square root with the number given, using the Boolean equal operator. If they match, then you have got a perfect square. 

In the second method, you have to use the floor and ceil function. You then compare the two, and if they match, then you have your perfect square. 

Also Read: Python Framework for Web Development

Top Data Science Skills to Learn in 2022

Conclusion

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.

Want to share this article?

Prepare for a Career of the Future

Leave a comment

Your email address will not be published. Required fields are marked *

Leave a comment

Your email address will not be published. Required fields are marked *

×
Get Free career counselling from upGrad experts!
Book a session with an industry professional today!
No Thanks
Let's do it
Get Free career counselling from upGrad experts!
Book a Session with an industry professional today!
Let's do it
No Thanks