Optimized solutions in Python for All Divisors and Prime Number

by

In the previous article we explored programs for obtaining all divisors of a given number. Let us see the ways in which we can discuss optimize the programs in the previous article as well as the program for Prime Numbers. Optimizing programs in recent usage or legacy code is important as we gain new knowledge or need to work with different dimensions or create more effective programs. Let us first explore the limitations of the programs.

Implementation of Optimized solutions in Python for All Divisors and Prime Number

n=int(input("Enter n: "))
for x in range(1,n+1):
    if n%x==0:
       print(x)

The program we have seen earlier for determining divisors does the tasks as expected. However, there is a huge problem or drawback with this kind of program. Suppose the user provided a very big number to the program as part of the input, it would run for very long while also leading to increased memory usage. How can we optimize the program?

Here is our optimized solution:

n=int(input("Enter n :"))
x=1
while x*x < n:
    if n%x == 0:
        print(x)
        print(n/x)
        x=x+1
if x*x==n:
    print(x)

Output:
Enter n :15
1
15.0

The reason this program works much better is that we can write all divisors of a number in pairs. For every pair (x,y), x*y=n. We can use similar improvements for determining the prime numbers.

In the next article we will have an advanced look at some of the in-built Python functions.

Leave a Comment