Querying the Maximum Number of Divisors in a Given Range

In number theory, the study of divisors of numbers is an interesting and important area. When dealing with a range of numbers (say from a to b), it can be useful to find out which number in that range has the maximum number of divisors. This blog post will explore different approaches to solve this problem, including common and best practices, along with example usage.

Table of Contents#

  1. Understanding Divisors
  2. Brute - Force Approach
  3. Optimized Approach using Prime Factorization
  4. Best Practices
  5. Example Usage
  6. References

1. Understanding Divisors#

A divisor of a number n is an integer d such that n % d == 0. For example, the divisors of 12 are 1, 2, 3, 4, 6, and 12. The number of divisors of a number can vary widely. Smaller numbers can have a relatively small number of divisors, while some larger numbers (especially those with many prime factors) can have a large number of divisors.

2. Brute - Force Approach#

Algorithm#

  • For each number n in the given range [a, b]:
    • Initialize a counter for the number of divisors to 0.
    • Iterate from 1 to n (inclusive).
    • For each i in this iteration, check if n % i == 0. If it is, increment the divisor counter.
  • Keep track of the number n with the maximum divisor count.

Example Code (Python)#

def count_divisors_brute_force(n):
    count = 0
    for i in range(1, n + 1):
        if n % i == 0:
            count += 1
    return count
 
 
def find_max_divisors_brute_force(a, b):
    max_count = 0
    num_with_max = a
    for num in range(a, b + 1):
        current_count = count_divisors_brute_force(num)
        if current_count > max_count:
            max_count = current_count
            num_with_max = num
    return num_with_max, max_count
 
 
a = 1
b = 100
result_num, result_count = find_max_divisors_brute_force(a, b)
print(f"The number {result_num} in the range [{a}, {b}] has {result_count} divisors.")

Limitations#

  • Time Complexity: The time complexity of the count_divisors_brute_force function is $O(n)$ for a single number n. When applied to a range of size m (where m = b - a+1), the overall time complexity is $O(mn)$. For large ranges (e.g., a = 1 and b = 10^6), this approach is extremely slow.

3. Optimized Approach using Prime Factorization#

Prime Factorization Basics#

Prime factorization of a number n is the expression of n as a product of prime numbers. For example, the prime factorization of 12 is $2^2\times3^1$.

Formula for Number of Divisors#

If the prime factorization of a number n is $n = p_1^{e_1}\times p_2^{e_2}\times\cdots\times p_k^{e_k}$, where p_i are prime numbers and e_i are their respective exponents, then the number of divisors of n is given by the formula $\tau(n)=(e_1 + 1)\times(e_2 + 1)\times\cdots\times(e_k + 1)$

Algorithm#

  • For each number n in the range [a, b]:
    • Perform prime factorization of n.
    • Calculate the number of divisors using the formula $\tau(n)=(e_1 + 1)\times(e_2 + 1)\times\cdots\times(e_k + 1)$.
  • Keep track of the number n with the maximum divisor count.

Example Code (Python)#

import math
 
 
def prime_factorization(n):
    factors = {}
    while n % 2 == 0:
        factors[2] = factors.get(2, 0)+1
        n = n // 2
    i = 3
    while i <= math.isqrt(n)+1:
        while n % i == 0:
            factors[i] = factors.get(i, 0)+1
            n = n // i
        i += 2
    if n > 1:
        factors[n] = 1
    return factors
 
 
def count_divisors_prime_factorization(n):
    factors = prime_factorization(n)
    count = 1
    for exp in factors.values():
        count *= (exp + 1)
    return count
 
 
def find_max_divisors_prime_factorization(a, b):
    max_count = 0
    num_with_max = a
    for num in range(a, b + 1):
        current_count = count_divisors_prime_factorization(num)
        if current_count > max_count:
            max_count = current_count
            num_with_max = num
    return num_with_max, max_count
 
 
a = 1
b = 100
result_num, result_count = find_max_divisors_prime_factorization(a, b)
print(f"The number {result_num} in the range [{a}, {b}] has {result_count} divisors.")

4. Best Practices#

Pre - computing Primes (for Larger Ranges)#

For very large ranges (e.g., a = 1 and b = 10^8), pre - computing prime numbers using the Sieve of Eratosthenes can be beneficial. This allows for faster prime factorization.

Memoization#

If the same numbers are being queried multiple times (e.g., in a program with multiple range queries), memoizing the results of prime factorizations and divisor counts can save a significant amount of time.

5. Example Usage#

Suppose we want to find the number with the maximum number of divisors in the range [1, 1000]. Using the prime factorization approach:

a = 1
b = 1000
result_num, result_count = find_max_divisors_prime_factorization(a, b)
print(f"The number {result_num} in the range [{a}, {b}] has {result_count} divisors.")

This will give us the number (in this case, 840) which has 32 divisors.

6. References#

2026-07