Finding Divisors Efficiently#

Here’s a basic way to count the divisors of a number:

number = 24
count = 0

for i in range(1, number + 1):
    if number % i:
        count += 1

return count

This method has a time complexity of O(n), which can be slow for large numbers. Observing the divisors of 24, we notice a pattern:

1 x 24
2 x 12
3 x 8
4 x 6

6 x 4
8 x 3
12 x 3
24 x 1

See the pattern. After the midpoint, the divisors repeat in reverse. We can leverage this pattern to reduce the complexity to O(sqrt(n)). Here’s an optimized method:

number = 24
count = 0

i = 1
while i * i < number + 1:
    if number % i:
        print("Divisor", i, n / i)
        count += 1
        # This condition is added for perfect squares
        # Say 36, one of its divisor would be 6 * 6
        # For this reason we have condition here for it
        # Which can be handy when taking sum of divisors
        if n / i != i:
            count += 1
    i += 1

return count

Greatest Common Divisor(GCD)#

The Greatest Common Divisor (GCD), also known as the Highest Common Factor (HCF), is the largest number that can divide two numbers without leaving a remainder. For example, the GCD of 4 and 12 is 4, since 4 is the largest number that divides both 4 and 12 without a remainder.

Typically, GCD is found using prime factorization, but efficient algorithms like the Euclidean algorithm can be used for larger numbers.

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

# Example
print("GCD of 4 and 12:", gcd(4, 12))