HiveBrain v1.2.0
Get Started
← Back to all entries
patternpythonMinor

Find highly composite number using Python 3

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
numberhighlyusingcompositefindpython

Problem

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.

Solution

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.

Code Snippets

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

Context

StackExchange Code Review Q#156986, answer score: 6

Revisions (0)

No revisions yet.