How to find amicable numbers – Python Program to Check Whether the given Two Numbers are Amicable Numbers or Not

How to find amicable numbers: Wondering how to find if two numbers given are Amicable or Not? Then, you have come the right way as we will explain what are Amicable Numbers and Python Program to Check if Two Numbers are Amicable Numbers or not. Refer to the Various Methods for Checking if given Numbers are Amicable or Not and use the method you are comfortable with.

Amicable Numbers in Python

First and foremost, what exactly is this Amicable? We say two numbers are Amicable if the sum of their proper divisors is equal to the opposite numbers, that is, the sum of x’s divisors is equal to y and the sum of y’s divisors is equal to x. We can grasp it better by using an example.

Take 234 and 339 as two numbers; now find the divisors of 123 and 456; their sums will be sum1 and sum2, respectively. Then sum2 must equal 123 and sum1 must equal 456.

We should determine all the suitable divisors of x ,y and add them separately before matching them to the opposite numbers; if they match, we claim the two numbers are amicable; otherwise, we say they are not.

sumX=y,

sumY=x

Where sumX is the sum of all proper divisors of the number x.

Where sumY is the sum of all proper divisors of the number y.

Examples:

Example 1:

Input:

given number1 =220 ;       given number2=284

Output:

The given numbers 220 and 284 are amicable numbers

Example 2:

Input:

given number1= 339    ; given number2=134

Output:

The given numbers 339 and 134 are not amicable numbers

Python Program to Check Whether the given Two Numbers are Amicable Numbers or Not

There are several ways to check whether the given number is given Two Number are Amicable Numbers or Not, some of them are:

Drive into Python Programming Examples and explore more instances related to python concepts so that you can become proficient in generating programs in Python Programming Language.

All of the methods follow a similar technique but differ in terms of time complexity. Methods for obtaining divisors are classified below based on their time complexity:

Method #1: Iterating from 2 to N-1

Approach:

  • Take both integers and store them in different variables.
  • Calculate the sum of the proper divisors of both numbers ( loop from 2 to given_number-1, keep track of the sum of the number’s proper divisors)
  • Repeat the above step for number2
  • Examine whether the total of the proper divisors equals the opposite numbers.
  • They are amicable numbers if they are equal.
  • The final result should be printed.

Below is the implementation:

Python Program to Check Whether the Given Numbers are Amicable Numbers or Not

# python program to cheeck whether the given number is Amicable numbers or not

# function which returns true if the given number is
# Amicable numbers else it will return False


def checkAmicableNumb(given_numb1, given_numb2):
    # Taking a variable totalSum1 and initializing it with 1
    totalSum1 = 1
    # Iterating from 2 to n-1
    for i in range(2, given_numb1):
        # if the iterator value is divides the number then add the given
        # number to totalSum1
        if given_numb1 % i == 0:
            totalSum1 += i
    # repeating the same step for number 2
    # Taking a variable totalSum2 and initializing it with 1
    totalSum2 = 1
    # Iterating from 2 to n-1
    for i in range(2, given_numb2):
        # if the iterator value is divides the number then add the given
        # number to totalSum2
        if given_numb2 % i == 0:
            totalSum2 += i

    # if the totalSum1 is equal to the given number2 and
    # totalSum2 is equal to the given number1 then both the numbers are amicable numbers
    # else they are not amicable numbers

    if(totalSum1 == given_numb2 and totalSum2 == given_numb1):
        # if it is true then they are amicable numbers so return true
        return True
    # if nothing is returned then they are not a amicable numbers so return False
    return False


# Given two numbers
# given number1(numb1)
given_numb1 = 220
# given number2(numb2)
given_numb2 = 284
# passing the given two numbers to checkAmicableNumb to check whether it is
# Amicable numbers or not
if(checkAmicableNumb(given_numb1, given_numb2)):
    print("The given numbers", given_numb1, "and",
          given_numb2, "are amicable numbers")
else:
    print("The given numbers", given_numb1, "and",
          given_numb2, "are not amicable numbers")

Output:

The given numbers 220 and 284 are amicable numbers

It requires O(n) Time Complexity.

Method #2:Iterating from 2 to N/2

Approach:

  • Take both integers and store them in different variables.
  • Calculate the sum of the proper divisors of both numbers ( loop from 2 to given_number//2, keep track of the sum of the number’s proper divisors)
  • Repeat the above step for number2
  • Examine whether the total of the proper divisors equals the opposite numbers.
  • They are amicable numbers if they are equal.
  • The final result should be printed.

Below is the implementation:

# python program to cheeck whether the given number is Amicable numbers or not

# function which returns true if the given number is
# Amicable numbers else it will return False


def checkAmicableNumb(given_numb1, given_numb2):
    # Taking a variable totalSum1 and initializing it with 1
    totalSum1 = 1
    # Iterating from 2 to n-1
    for i in range(2, given_numb1//2 + 1):
        # if the iterator value is divides the number then add the given
        # number to totalSum1
        if given_numb1 % i == 0:
            totalSum1 += i
    # repeating the same step for number 2
    # Taking a variable totalSum2 and initializing it with 1
    totalSum2 = 1
    # Iterating from 2 to n-1
    for i in range(2, given_numb2//2 + 1):
        # if the iterator value is divides the number then add the given
        # number to totalSum2
        if given_numb2 % i == 0:
            totalSum2 += i

    # if the totalSum1 is equal to the given number2 and
    # totalSum2 is equal to the given number1 then both the numbers are amicable numbers
    # else they are not amicable numbers

    if(totalSum1 == given_numb2 and totalSum2 == given_numb1):
        # if it is true then they are amicable numbers so return true
        return True
    # if nothing is returned then they are not a amicable numbers so return False
    return False


# Given two numbers
# given number1(numb1)
given_numb1 = 220
# given number2(numb2)
given_numb2 = 284
# passing the given two numbers to checkAmicableNumb to check whether it is
# Amicable numbers or not
if(checkAmicableNumb(given_numb1, given_numb2)):
    print("The given numbers", given_numb1, "and",
          given_numb2, "are amicable numbers")
else:
    print("The given numbers", given_numb1, "and",
          given_numb2, "are not amicable numbers")

Output:

The given numbers 220 and 284 are amicable numbers

It requires O(n) Time Complexity.

It reduces half the number of iterations.

Method #3: Efficient Approach (Iterating till Square root of N)

Approach:

  • Take both integers and store them in different variables.
  • Calculate the sum of the proper divisors of both numbers (go through the numbers till you get to the square root of n. If a number i divides n, then sum both i and n/i)
  • Repeat the above step for number2
  • Examine whether the total of the proper divisors equals the opposite numbers.
  • They are amicable numbers if they are equal.
  • The final result should be printed.

Below is the implementation:

# python program to cheeck whether the given number is Amicable numbers or not

# function which returns true if the given number is
# Amicable numbers else it will return False


def checkAmicableNumb(given_numb1, given_numb2):
    # Taking a variable totalSum1 and initializing it with 1
    totalSum1 = 1
    k = 2
    while k * k <= given_numb1:
        # if the iterator value is divides the number then add the given number to totalSum
        if given_numb1 % k == 0:
            totalSum1 = totalSum1 + k + given_numb1/k
        k += 1
    # repeating the same step for number 2
    # Taking a variable totalSum2 and initializing it with 1
    totalSum2 = 1
    k = 2
    while k * k <= given_numb2:
        # if the iterator value is divides the number then add the given number to totalSum
        if given_numb2 % k == 0:
            totalSum2 = totalSum2 + k + given_numb2/k
        k += 1

    # if the totalSum1 is equal to the given number2 and
    # totalSum2 is equal to the given number1 then both the numbers are amicable numbers
    # else they are not amicable numbers

    if(totalSum1 == given_numb2 and totalSum2 == given_numb1):
        # if it is true then they are amicable numbers so return true
        return True
    # if nothing is returned then they are not a amicable numbers so return False
    return False


# Given two numbers
# given number1(numb1)
given_numb1 = 220
# given number2(numb2)
given_numb2 = 284
# passing the given two numbers to checkAmicableNumb to check whether it is
# Amicable numbers or not
if(checkAmicableNumb(given_numb1, given_numb2)):
    print("The given numbers", given_numb1, "and",
          given_numb2, "are amicable numbers")
else:
    print("The given numbers", given_numb1, "and",
          given_numb2, "are not amicable numbers")

Output:

The given numbers 220 and 284 are amicable numbers

Here the given numbers 220 and 284 are amicable numbers.

This is the efficient approach to do the same problem quickly compared to the first two methods.

It requires O(Sqrt(n)) Time Complexity.

Related Programs: