5 Best Ways to Check if Count of Divisors is Even or Odd in Python

by

💡 Problem Formulation: This article focuses on assessing whether a given integer’s count of divisors is even or odd utilizing various methods in Python. For example, if the integer is 10, its divisors are 1, 2, 5, and 10, hence the count (4) is even.

Method 1: Brute Force Approach

This method involves a straightforward approach that counts all divisors of a number by iterating through the range from 1 to the number itself and checking if there’s no remainder upon division. The function specification would count the number of divisors and determine the parity of their count.

Here’s an example:

def count_divisors_even_odd(n):
    count = 0
    for i in range(1, n+1):
        if n % i == 0:
            count += 1
    return "Even" if count % 2 == 0 else "Odd"

# Example use:
print(count_divisors_even_odd(10))

Output: Even

This snippet defines a function count_divisors_even_odd which iterates through all numbers from 1 to n and increments a count variable if a divisor is found. It then checks if count is even or odd, returning the corresponding string.

Method 2: Square Root Optimization

The Square Root Optimization method improves on the brute force approach by only iterating up to the square root of the number. Since divisors come in pairs, this method counts each pair only once, significantly reducing the number of iterations required for large numbers.

Here’s an example:

import math

def count_divisors_even_odd_sqrt(n):
    count = 0
    sqrt_n = int(math.sqrt(n))
    for i in range(1, sqrt_n + 1):
        if n % i == 0:
            count += 1 if i * i == n else 2
    return "Even" if count % 2 == 0 else "Odd"

# Example use:
print(count_divisors_even_odd_sqrt(10))

Output: Even

The count_divisors_even_odd_sqrt function checks for divisors only up to the square root of n, doubling the count for each divisor pair. If a number is a perfect square, it only increments the count by one for the matched pair, and then determines the parity of the divisor count.

Method 3: Efficient Divisor Count with Sieve

Utilizing the Sieve of Eratosthenes algorithm, an efficient way to pre-calculate the count of divisors for a range of numbers can be performed. This is particularly useful when the even or odd check has to be done on multiple numbers within a range.

Here’s an example:

def sieve_divisor_count(limit):
    divisors_count = [0] * (limit+1)
    for i in range(1, limit+1):
        for j in range(i, limit+1, i):
            divisors_count[j] += 1
    return divisors_count

# Example use:
divisors_count = sieve_divisor_count(10)
n = 10
print("Even" if divisors_count[n] % 2 == 0 else "Odd")

Output: Even

This example pre-calculates the count of divisors for all numbers up to a specified limit using a sieve-like approach and stores them in divisors_count. The parity of the divisor count for any number within the limit can be retrieved in constant time from this list.

Method 4: Mathematical Insight

Using a mathematical insight, we know that all numbers have an even number of divisors, except for perfect squares, which have an odd number. This method employs a simple check to see if the number is a perfect square to determine the parity of the divisor count.

Here’s an example:

import math

def is_even_divisors_math(n):
    sqrt_n = int(math.sqrt(n))
    return "Even" if sqrt_n * sqrt_n != n else "Odd"

# Example use:
print(is_even_divisors_math(10))

Output: Even

The function is_even_divisors_math calculates the square root of n and checks whether the square of this integer square root is equal to n. If they’re equal, the number is a perfect square with an odd number of divisors; otherwise, it has an even number of divisors.

Bonus One-Liner Method 5: Lambda Function

A one-liner approach using a lambda function combines Method 4’s mathematical insight. It’s a concise and elegant solution suitable for inline use without the need for a dedicated function definition.

Here’s an example:

import math

# Example use:
print((lambda n: "Even" if int(math.sqrt(n)) ** 2 != n else "Odd")(10))

Output: Even

The one-liner lambda function takes n as an argument and performs the same operation as Method 4, outputting “Even” or “Odd” based on whether n is a perfect square.

Summary/Discussion

  • Method 1: Brute Force Approach. Simple and intuitive method. Best suited for small numbers. It can be inefficient for larger numbers due to many iterations.
  • Method 2: Square Root Optimization. This is a much faster approach than the brute force method. It still has the overhead of iteration but handles large numbers better.
  • Method 3: Efficient Divisor Count with Sieve. Ideal for multiple queries on a range of numbers. Requires upfront computation, which can be costly if only one or few numbers are checked.
  • Method 4: Mathematical Insight. Extremely efficient method with constant time complexity. However, it requires understanding that only perfect squares have an odd number of divisors.
  • Method 5: Lambda Function. Quick and concise for inline usage. However, lacks readability, and reusability compared to other methods.