10
\$\begingroup\$

A highly composite number (HCN) is a positive integer with more divisors than any smaller positive integer ha according to Wikipedia. Here is a YouTube video about it.

def get_divisors(number_range):
  divisor_list = []
  divisor_list2 = []
  for number in range(1,number_range+1):
    for e in range(1,number_range+1):
      if number % e == 0:
        divisor_list2.append(e)
    divisor_list.append(divisor_list2)
    divisor_list2 = []
  return divisor_list

def get_highly_composite_number(number_range):
  divisor_list = get_divisors(number_range)
  highly_composite_number_list = []
  number_of_divisor_list = []
  number_of_divisor_list2 = []
  number_of_divisor_list3 = []
  tracker = 0
  for e in divisor_list:
    number_of_divisor_list.append(len(e))
    number_of_divisor_list2.append(max(number_of_divisor_list))
  for e in number_of_divisor_list2:
    number_of_divisor_list3.append(e)
    if number_of_divisor_list3[tracker] == max(number_of_divisor_list3) and number_of_divisor_list3.count(number_of_divisor_list3[tracker]) == 1:
      highly_composite_number_list.append(tracker+1)
      tracker += 1
    else:
      tracker += 1
  return highly_composite_number_list

I know the naming is horrible, but I did not know any better ways. Also, I know this can probably be condensed, but I did not want to touch it.

\$\endgroup\$
6
\$\begingroup\$

As you said, the naming is not good and the code can be condensed and optimized.

  • You don't need to keep all the lists, you just need the count
  • You can split get_divisors so you have another function to get the divisors of a single number
  • You can use a dictionary to store the divisor count of the numbers.

This would already take care of the variable names:

def get_divisors_count(number):
  divisors = []
  for divisor in range(1, number + 1):
    if (number % divisor) == 0:
      divisors.append(divisor)
  return len(divisors)

def get_divisors_range(number_range):
  divisor_count = {}
  for number in range(1, number_range):
    divisor_count[number] = get_divisors_count(number)
  return divisor_count

def get_highly_composite_number(number_range):
  divisor_list = get_divisors_range(number_range)
  highly_composite_number_list = []
  for i in range(number_range - 1, 0, -1):
    found = False
    for j in range(1, i):
      if (divisor_list[j] >= divisor_list[i]):
        found = True
        break
    if (not found):
      #If you want the list sorted from low to high
      #change this to highly_composite_number_list.insert(0, i)
      highly_composite_number_list.append(i)
  return highly_composite_number_list
  • This could also be optimized a bit using a lookup for numbers of which you already computed the divisors. For examples, 4 is a divisor of 8, but when you check 8, you can lookup the divisors of 4 and use that.
\$\endgroup\$
6
\$\begingroup\$

The first thing I spotted when I saw your code was the indentation. In python, you should use 4 spaces per indentation level. More, you should have 2 new lines between your methods and keep your lines no longer than 120 characters (in PEP 8 - which is the official python style-guide, the limit is of 79 characters but I like to stick with InteliJ's recommendation).

More, based on ChatterOne's answer I'd rewrite his first two functions as follows:

def get_divisors_count(number):
    """What does this function do?"""
    return len([divisor for divisor in range(1, number + 1) if (number % divisor) == 0])


def get_divisors_range(number_range):
    """What does this function do?"""
    return {number: get_divisors_count(number) for number in range(1, number_range)}

In the first function I've used list comprehension and in the second one dictionary comprehension. You can read more about them (and their advantages) here and here

Last but not least, you should definitely add docstrings to your functions to describe their functionality.

Another thing you might do is adding the if __name__ == '__main__' guard.

\$\endgroup\$
  • \$\begingroup\$ Why not sum(1 for divisor in range(1, number + 1) if (number % divisor) == 0)? \$\endgroup\$ – 409_Conflict Mar 6 '17 at 9:35
  • \$\begingroup\$ @MathiasEttinger I thought of this too, but if you'll benchmark the two, (yours and mine), you'll get a slightly better time for list comprehension. See here. \$\endgroup\$ – Grajdeanu Alex. Mar 6 '17 at 9:57
  • \$\begingroup\$ Interestingly enough, timings tend to be the same if you setup the test to look like the actual computation: repl.it/GIbq/1 \$\endgroup\$ – 409_Conflict Mar 6 '17 at 10:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.