How to improve this solution?

Question

Divisors of 42 are : 1, 2, 3, 6, 7, 14, 21, 42. These divisors squared are: 1, 4, 9, 36, 49, 196, 441, 1764. The sum of the squared divisors is 2500 which is 50 * 50, a square!

Given two integers m, n (1 <= m <= n) we want to find all integers between m and n whose sum of squared divisors is itself a square. 42 is such a number.

The result will be an array of arrays, each subarray having two elements, first the number whose squared divisors is a square and then the sum of the squared divisors.

Examples:

list_squared(1, 250) --> [[1, 1], [42, 2500], [246, 84100]]

list_squared(42, 250) --> [[42, 2500], [246, 84100]]

above is the instructor of the question.

I have a problem when do the practice of Coderwars. my code have passed all tests, but have a error "timeout", it means my code is not very good.how can I improve it. Below is my solution.

from math import sqrt
def get_div(x):
    s = []
    for i in range(1,x):
        if x%i == 0:
            # print i, x/i
            s.append(i)
            s.append(x/i)
    return set(s)

def list_squared(m, n):
    p = []
    for i in range(m,n):
        if i == 1:
            p.append([1,1])
            continue
        s = sum(a**2 for a in get_div(i))
        if float(sqrt(s)).is_integer():
            p.append([i,s])
    return p

Try : codereview.stackexchange.com for optimizing your code. — MooingRawr, Oct 26 '16 at 16:07
In `get_div` you don't need to search for numbers > x/2, as they will never be divisors. And afaik you only need to check numbers <= x/4. And then you shouldn't need to use a set. — xZise, Oct 26 '16 at 16:13
I think you only have to go up to the sqrt of x in your get_div function. — Hoopdady, Oct 26 '16 at 16:13
@xZise this solution will make something wrong below the function — Xue Chuancong, Oct 26 '16 at 17:02

score 1 · Answer 1 · answered Oct 26 '16 at 16:21

1

Two things I would suggest:

1) Instead of get_div and returning an array, why not change it to get_div_squared_sum and just return the sum? You're only using that array to sum anyway so if you just calculate the sum in the function then you lose an entire for loop.

2) It's been mentioned already but you only need to go to sqrt(x) in order to get every possible divisor.

answered Oct 26 '16 at 16:21

Devin White

31
3

thank your suggest, it works well, but it takes longer than 12000ms to solve the final test. I think it is the test make something wrong. – Xue Chuancong Oct 26 '16 at 16:53

score 1 · Accepted Answer · edited May 23 '17 at 12:16

Based on the answer to this question Algorithm to calculate the number of divisors of a given number and the comment from @devin-white you may want to try the following solution.

def divisors_squared_sum(x):
    limit = x
    squared_sum = 0
    if x==1:
        return 1
    i = 1
    while True:
        if x % i == 0:
            limit = x / i
            if limit != i:
                squared_sum += limit**2
            squared_sum += i**2
        i += 1
        if i >= limit:
            return squared_sum

def list_squared2(start, end):
    res = []
    for i in xrange(start, end):
        squared_sum = divisors_squared_sum(i)
        sqrt_sum = np.sqrt(squared_sum)
        if int(sqrt_sum) == sqrt_sum:
            res.append([i, squared_sum])

    return res

I get the following results:

In [24]: %timeit list_squared(1, 250)
100 loops, best of 3: 3.6 ms per loop

In [25]: %timeit list_squared2(1, 250)
100 loops, best of 3: 1.96 ms per loop

thank you very much, your solution solve my problem.it is longer than my code.I will learn more about it. — Xue Chuancong, Oct 27 '16 at 04:40

How to improve this solution?

2 Answers2