Y
Y
Yura Khlyan2015-06-16 11:58:13
Python
Yura Khlyan, 2015-06-16 11:58:13

How to improve the speed of the function?

Good time of the day.
My task is as follows: select all pairs of numbers (a, b) smaller than n that satisfy the condition: a * b == (sum(1..n) - a - b). The pairs (a, b) and (b, a) are different.
I wrote the code, but it's too slow. What can you advise?

def removNb(n):
    return [(a, b)  for a in range(n+1) for b in range(n+1) if sum(range(n+1)) - a - b == a * b]

Answer the question

In order to leave comments, you need to log in

1 answer(s)
M
Mrrl, 2015-06-16
@MAGistr_MTM

Write the condition as (a+1)*(b+1) == n*(n+1)/2+1 = N, and for numbers a from (n+1)/2 to n check if N is divisible to a+1. If divisible, then b=N/(a+1)-1. Just in case, check that b < n+1.
If desired, the enumeration can be reduced by about 12 times. But then, instead of checking divisibility, it would be necessary to quickly check whether the number is a perfect square - which may not be very simple.

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question