3
\$\begingroup\$

I'm new to Python! Kindly suggest me improvements!

Problem statement :

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number. A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

My Work:

import math    
dict = {}


def get_divisors_sum(num):
    list  = []
    for i in range(1, int(math.sqrt(num)+1), 1):
        if (num%i==0):
            b = num/i
            if (i==b):
                list.append(i)
            else:
                list.append(i)
                list.append(b)
    return sum(list) - num

# print get_divisors(28)


def generate_abundant_numbers():
    list = []
    for i in range(1, 28123, 1):
        if get_divisors_sum(i) > i:
            list.append(i)
    return list



def insert_to_dictionary():
    global dict
    list = generate_abundant_numbers()
    for i in range(0, len(list) - 1, 1):
        for j in range(i, len(list), 1):
            dict[list[i] + list[j]] = 1
    print dict


def print_answer():
    sum = 0
    for i in range(1, 28123, 1):
        if i not in dict:
            print i
            sum += i
    print sum


insert_to_dictionary()
print_answer()
\$\endgroup\$
  • \$\begingroup\$ See this answer for some ideas about how to speed this up. \$\endgroup\$ – Gareth Rees Jun 14 '16 at 8:57
4
\$\begingroup\$

set

You build a dictionary to take advantage of the fast \$O(1)\$ membership test of the keys, but you never use the value (that is always 1), so you could just use a set that has the same \$O(1)\$ membership test but no values.

Returning the result

It is standard practice to return the results, not print them. If a result is returned, the user of the function may decide to do anything with it, including printing it. If you just print the result, no further re-use is possible.

Avoid globals when unnecessary

Globals may be changed anytime, from anywhere in your program. If you modify a global once wrongly by accident the whole program goes bogus. Just return the dict from insert_to_dictionary (I would call it abundant_sums because types should be in names and it is more descriptive.)

Use the built-ins

sum = 0
for i in range(1, 28123, 1):
    if i not in dict:
        print i
        sum += i
print sum

Becomes:

return sum(i for i in range(1, 28123, 1) if i not in set_)

I also avoided printing long lists of numbers because is not required (just the final answer is required).

\$\endgroup\$
  • \$\begingroup\$ so you mean to say, set in Python is equivalent to HashSet in Java? \$\endgroup\$ – Mayur Kulkarni Jun 15 '16 at 2:22
  • 1
    \$\begingroup\$ Yes, Java Hashset also offers "constant time performance for the basic operations (add, remove, contains and size)," (from Java docs docs.oracle.com/javase/7/docs/api/java/util/HashSet.html) \$\endgroup\$ – Caridorc Jun 20 '16 at 12:24

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.