5 Effective Ways to Find Common Divisors of Two Numbers in Python

💡 Problem Formulation: We often encounter a situation where we need to find common factors or divisors of two given integers. This is a common requirement in various mathematical computations and coding challenges. For example, given the numbers 12 and 18, we want to know the total number of common divisors, which in this case are 1, 2, 3, and 6. So the desired output is 4.

Method 1: Brute Force Approach

This method involves iterating through all numbers from 1 to the minimum of the two numbers and checking whether both numbers are divisible by the iterating number. It is a straightforward approach and easy to implement, although not the most efficient for large numbers.

Here’s an example:

def count_common_divisors(num1, num2): 
    common_divisors_count = 0
    for i in range(1, min(num1, num2) + 1):
        if num1 % i == num2 % i == 0:
            common_divisors_count += 1
    return common_divisors_count

print(count_common_divisors(12, 18))

Output: 4

The code snippet demonstrates the counting of common divisors between two numbers using a simple for loop and modulo operator to identify divisors.

Method 2: Using Euclidean Algorithm

This method uses the Euclidean algorithm to compute the greatest common divisor (GCD) first, and then counts the number of divisors of the GCD. As the GCD is the largest common divisor, all its divisors are common to the two given numbers. This method is far more efficient for larger numbers.

Here’s an example:

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def count_common_divisors(num1, num2):
    gcd_value = gcd(num1, num2)
    divisors = [i for i in range(1, gcd_value + 1) if gcd_value % i == 0]
    return len(divisors)

print(count_common_divisors(12, 18))

Output: 4

By applying the Euclidean algorithm to find the GCD followed by counting its divisors, this snippet efficiently calculates the number of common divisors between the two numbers.

Method 3: Optimized Divisors Function

Improving efficiency by reducing the range of numbers to check. By understanding that a divisor larger than the square root could not pair up to form the original number, we limit our search to the square root of the smaller number and count each valid pair of divisors, ensuring we count only unique pairs.

Here’s an example:

def count_common_divisors(num1, num2): 
    common_divisors_count = 0
    for i in range(1, int(min(num1, num2) ** 0.5) + 1):
        if num1 % i == 0 and num2 % i == 0:
            common_divisors_count += 2 if num1 // i != i else 1
    return common_divisors_count

print(count_common_divisors(12, 18))

Output: 4

This snippet iterates only up to the square root of the smaller number, checks for common divisors, and increments the count considering both the divisor and its complement.

Method 4: Using Sets for Common Divisors

By creating sets of divisors for each number and finding the intersection, we can calculate the common divisors. Though not the most efficient for large numbers, it is an elegant and easy-to-understand approach.

Here’s an example:

def divisors_set(num):
    return set(i for i in range(1, num + 1) if num % i == 0)

def count_common_divisors(num1, num2): 
    return len(divisors_set(num1).intersection(divisors_set(num2)))

print(count_common_divisors(12, 18))

Output: 4

This snippet cleanly illustrates the usage of sets and their intersection to find common divisors, effectively utilizing built-in Python functionality.

Bonus One-Liner Method 5: Using Functional Programming

A compact one-liner that combines list comprehension, the gcd() function from Python’s math module, and a lambda function to count the common divisors in a single expression. It’s not only concise but also takes advantage of Python’s functional programming capabilities.

Here’s an example:

from math import gcd

count_common_divisors = lambda num1, num2: sum(1 for i in range(1, gcd(num1, num2) + 1) if num1 % i == 0 and num2 % i == 0)
print(count_common_divisors(12, 18))

Output: 4

This one-liner defines a lambda function that calculates the number of common divisors using gcd() and list comprehension, offering an elegant solution with minimal code.

Summary/Discussion

Method 1:

Method 2:

Method 3:

Method 4:

Bonus Method 5: