Python: Division by larger numbers slower?
Question: Why does dividing by the larger factor pair result in slower execution?

My solution for
<https://codility.com/programmers/task/min_perimeter_rectangle/>

    
    
    from math import sqrt, floor
    
    # This fails the performance tests
    def solution_slow(n):
        x = int(sqrt(n))
        for i in xrange(x, n+1):
            if n % i == 0:
                return 2*(i + n / i))
    
    # This passes the performance tests
    def solution_fast(n):
        x = int(sqrt(n))
        for i in xrange(x, 0, -1):
            if n % i == 0:
                return 2*(i + n / i)
    


Answer: It's not division that slows it down; it's the number of iterations required.

Let `L = xrange(0, x)` (order doesn't matter here) and `R = xrange(x, n+1)`.
Every factor of `n` in `L` can be paired with exactly one factor of `n` in
`R`. In general, `x` is much, much smaller than `n/2`, so `L` is much smaller
than `R`. This means that there are far more elements of `R` that don't divide
`n` than there are in `L`. In the case of a prime number, there _are_ no
factors, so the slow solution has to check every value of the much larger than
instead of the much smaller set.

