Python Examples

Python Program - Find all factors of a Number

Objective: Write a Python program to find all distinct factors (divisors) of a given natural number. The divisors of few numbers are given below:

 Number: 10
 Divisors: 1 2 5 10

 Number: 15
 Divisors: 1 3 5 15

 Number: 100
 Divisors: 1 2 4 5 10 20 25 50 100

Method 1: Using iteration

One of the basic approach is to iterate from 1 to n and in each iteration check whether the number divides n. If it divides then print it.

#function to print all divisors of a number
def printDivisors(n):
  print("Divisors of", n ,"are: ", end="")
  for i in range(1, n+1):
    if(n%i == 0):
      print(i, end=" ")
  print()

printDivisors(10)
printDivisors(50)
printDivisors(100)

The above code will give the following output:

Divisors of 10 are: 1 2 5 10 
Divisors of 50 are: 1 2 5 10 25 50 
Divisors of 100 are: 1 2 4 5 10 20 25 50 100

Method 2: Optimized Code

Instead of checking the divisibility of the given number from 1 to n, it is checked till square root of n. For a factor larger than square root of n, there must the a smaller factor which is already checked in the range of 1 to square root of n.

import math

#function to print all divisors of a number
def printDivisors(n):
  print("Divisors of", n ,"are: ", end="")
  #loop from 1 to math.sqrt(n)
  for i in range(1, int(math.sqrt(n)) + 1):
    if(n%i == 0):
      if(n/i == i):
        print(i, end=" ")
      else:
        print(i, n//i, end=" ")
  print()

printDivisors(10)
printDivisors(50)
printDivisors(100)

The above code will give the following output:

Divisors of 10 are: 1 10 2 5 
Divisors of 50 are: 1 50 2 25 5 10 
Divisors of 100 are: 1 100 2 50 4 25 5 20 10

Method 3: Optimized Code with sorted result

In the previous method, results are produced in a irregular fashion (printed in pairs - small number and large number). The result can be sorted by storing the larger number and print them later on. Consider the example below:

import math

#function to print all divisors of a number
def printDivisors(n):
  print("Divisors of", n ,"are: ", end="")
  
  #creating a list to store larger numbers
  list = []

  #loop from 1 to math.sqrt(n)
  for i in range(1, int(math.sqrt(n)) + 1):
    if(n%i == 0):
      if(n/i == i):
        print(i, end=" ")
      else:
        print(i, end=" ")
        #storing the large number of a pair
        list.append(int(n/i))
  
  #printing stored large numbers of pairs
  for i in list[::-1]:
    print (i, end =" ")
  print()

printDivisors(10)
printDivisors(50)
printDivisors(100)

The above code will give the following output:

Divisors of 10 are: 1 2 5 10 
Divisors of 50 are: 1 2 5 10 25 50 
Divisors of 100 are: 1 2 4 5 10 20 25 50 100

Method 4: Another Optimized Code

To produce the result in sorted order, we can iterate from 1 to square root of n and printing the number which divides n. After that we can iterate back (in reverse order) and printing the quotient of all numbers which divides n.

import math

#function to print all divisors of a number
def printDivisors(n):
  print("Divisors of", n ,"are: ", end="")
  #loop from 1 to math.sqrt(n)
  i = 0
  for i in range(1, int(math.sqrt(n))):
    if(n%i == 0):
      print(i, end=" ")

  for i in range(int(math.sqrt(n)), 0, -1):
    if(n%i == 0):
      print(n//i, end=" ")
  print()

printDivisors(10)
printDivisors(50)
printDivisors(100)

The above code will give the following output:

Divisors of 10 are: 1 2 5 10 
Divisors of 50 are: 1 2 5 10 25 50 
Divisors of 100 are: 1 2 4 5 10 20 25 50 100

Python Program - Find all factors of a Number

Method 1: Using iteration

Method 2: Optimized Code

Method 3: Optimized Code with sorted result

Method 4: Another Optimized Code

Recommended Pages