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.

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.

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.

Also Read: Python Framework for Web Development

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.

I hope you will learn a lot while working on this blog. If you are curious about learning data science to be in the front of fast-paced technological advancements, check out upGrad & IIIT-B’s PG Diploma in Data Science and upskill yourself for the future.

Prepare for a Career of the Future

UPGRAD AND IIIT-BANGALORE'S PG DIPLOMA IN DATA SCIENCE
Learn More

Leave a comment

Your email address will not be published.

×