range() vs xrange() Python2|3 issues for performance

[Steven D'Aprano]

harrismh777 wrote:

> def perf(n):
>      sum = 0
>      for i in range(1, n):
>          if n % i == 0:
>              sum += i
>      return sum == n


A more effective way to speed that up is with a better algorithm:

def isperfect(n):
    if n < 2: return False
    total = 1
    for i in range(2, int(n**0.5)+1):
        a, b = divmod(n, i)
        if b == 0:
            total += a+i
    return total == n
 
For n=33550336 it loops about 5791 times instead of 33550335, reducing the
amount of work done by about 99.98%. 

isperfect is fast enough to exhaustively test every number up to a low
limit: testing every number between 0 and 8128 inclusive took about 0.38
second in total on my PC. That's an average of 0.05 millisecond per number
tested. Unfortunately, it doesn't scale. isperfect(33550336) takes about
4.4 ms, and isperfect(8589869056) about 84 ms. 

However, it is still (barely) feasible to exhaustively test every number up
to a much higher range. I extrapolate that the time needed to check every
value between 0 and 33550336 would take about 30 hours.

If you're wondering why exhaustive testing is so expensive, it's because the
test code simply calls isperfect(n) for each n. The number of iterations in
each call to isperfect is approximately sqrt(n), so the total in any
exhaustive test is approximately sum(x**0.5 for x in range(upperlimit)), 
which gets rather large.


-- 
Steven