Searching the number with the biggest amount of odd divisors in an interval

Question

I wrote this program for school (first year in college) and it works, but it's too slow. I wondered if anyone could help me optimize this a bit, because I've been trying and trying, but it just won't get better.

If I choose a lower limit of 5000 and an upper limit of 10000 it my program 10 times longer than my professors code (I did not see his code).

This is for school, but I won't get a grade for this; I'm not even obligated to make it. I just really want to improve.

def askLowerLimit():
    lowerLimit = int(input())
    while lowerLimit <= 0:
        print()
        lowerLimit = int(input())
    return lowerLimit

def askUpperLimit(lowerLimit):
    upperLimit = int(input())
    while upperLimit < lowerLimit:
        print()
        upperLimit = int(input())
    return upperLimit

def amountOddDivisorsOf(number):
    amountOddDivisors = 1
    divisor = 2
    if number % 2 != 0:
        divisor = 3
    for i in range(3, number//divisor +1, 2):
        if number % i == 0:
            amountOddDivisors += 1
    return amountOddDivisors

def numberWithMostOddDivisors(lowerLimit, upperLimit):
    numberWithMostDivisors = lowerLimit
    amountOfNumberWithMostDivisors = amountOddDivisorsOf(numberWithMostDivisors)
    for x in range(lowerLimit + 1, upperLimit + 1):
        amountOfCurrentNumber = amountOddDivisorsOf(x)
        if amountOfCurrentNumber > amountOfNumberWithMostDivisors:
            numberWithMostDivisors = x
            amountOfNumberWithMostDivisors = amountOfCurrentNumber
    return numberWithMostDivisors

def biggestAmmountOddDivisorsInInterval():
    lowerLimit = askLowerLimit()
    upperLimit = askUpperLimit(lowerLimit)
    numberWithMostD = numberWithMostOddDivisors(lowerLimit, upperLimit)
    amountOfOddDivisorsOfNumber = amountOddDivisorsOf(numberWithMostD)
    print("Number with most odd divisors in interval [{0} {1}] is {2}:".format(lowerLimit, upperLimit, numberWithMostD))
    print("{0} has {1} odd divisors!".format(numberWithMostD, amountOfOddDivisorsOfNumber))

biggestAmmountOddDivisorsInInterval()

The problem should be somewhere in amountOddDivisorsOf(number) or numberWithMostOddDivisors(lowerLimit, upperLimit).

Answer 1

Bug

Your code isn't always correct:

>>> amountOddDivisorsOf(15)
3

Should be 4.

Coding style

The Python style guide recommends snake_case over camelCase. Also, many of your names are just WAY too long. You're taking up too much space without providing new information.

There's also a lot of repetitiveness. askLowerLimit() and askUpperLimit() shouldn't be separate functions. You should have one function prompting for a value, and then separately assert 0 < lower < upper.

Finding the most divisors

numberWithMostOddDivisors is extremely verbose. We can do much better. The max function takes a keyword argument named key that gives you a function. So as a first go, it's as easy as:

def most_odd_divisors(lo, hi):
    return max(range(lo, hi+1), key=num_odd_divisors)

But this is unsatisfactory, as then you have to recalculate how many odd divisors it has. So instead, we can use:

def most_odd_divisors(lo, hi):
    with_divs = ((i, num_odd_divisors(i)) for i in range(lo, hi+1))
    return max(with_divs, key=operator.itemgetter(1))

And that'll give you both the most odd divisors and the value:

lo = ask_limit()
hi = ask_limit()
assert hi > lo > 0
num, divisors = most_odd_divisors(lo, hi)

Better way of counting

Rather than manually counting each divisor, remember the number of factors formula. If \$n = \prod_p p^i\$, then the sum of the factors is \$\prod_p (i+1)\$, so the number of odd factors if \$\prod_{p \neq 2} (i+1)\$.

So let's find the prime factorization first. We'll just yield pairs of prime numbers and their exponents:

def prime_factors(n):
    for i in itertools.count(2):
        if i*i > n:
            break

        exp = 0
        while n%i == 0:
            n //= i
            exp += 1

        if exp > 0:
            yield i, exp

    if n > 1:
        yield n, 1

The advantage here is that we're not repeating a lot of work. Once you know that a number is divisible by 3 and 5, you know it'll be divisible by 15 too. This way, doing the bare minimum amount of divisibility checking - which isn't cheap!

We can use that to:

def num_odd_divisors(n):
    prod = 1
    for p, e in prime_factors(n):
        if p != 2:
            prod *= e+1
    return prod

Counting from 5,000 to 10,000, this is roughly 11x faster than your implementation. So I suspect your professor did something along these lines.