Optimizing Divisor Sieve

I have two sieves that I wrote in python and would like help optimizing them if at all possible. The divisorSieve calculates the divisors of all numbers up to n. Each index of the list contains a list of its divisors. The numDivisorSieve just counts the number of divisors each index has but doesn't store the divisors themselves. These sieves work in a similar way as you would do a Sieve of Eratosthenes to calculate all prime numbers up to n.

Note: divs[i j].append(i) changed from divs[i j] += [i] with speed increase thanks to a member over at stackoverflow. I updated the table below with the new times for divisorSieve. It was suggested to use this board instead so I look forward to your input.

def divisorSieve(n):
    divs = [[1] for x in xrange(0, n + 1)]
    divs[0] = [0]
    for i in xrange(2, n + 1):
        for j in xrange(1, n / i + 1):
            divs[i * j].append(i) #changed from += [i] with speed increase.
    return divs

    def numDivisorSieve(n):
        divs = [1] * (n + 1)
        divs[0] = 0
        for i in xrange(2, n + 1):
            for j in xrange(1, n / i + 1):
                divs[i * j] += 1
        return divs

#Timer test for function
if __name__=='__main__':
    from timeit import Timer
    n = ...
    t1 = Timer(lambda: divisorSieve(n))
    print n, t1.timeit(number=1)

Results:

```
-----n-----|--time(divSieve)--|--time(numDivSieve)--
100,000 | 0.333831560615 | 0.187762331281
200,000 | 0.71700566026 | 0.362314797537
300,000 | 1.1643773714 | 0.55124339118
400,000 | 1.63861821235 | 0.748340797412
500,000 | 2.06917832929 | 0.959312993718
600,000 | 2.52753840891 | 1.17777010636
700,000 | 3.01465945139 | 1.38268800149
800,000 | 3.49267338434 | 1.62560614543
900,000 | 3.98145114138 | 1.83002270324
1,000,000 | 4.4809342539 | 2.10247496423
2,000,000 | 9.80035361075 | 4.59150618897
3,000,000 | 15.465184114 | 7.24799900479
4,000,0

You can use xrange's third param to do the stepping for you to shave off a little bit of time (not huge).

Changing:

for j in xrange(1, n / i + 1):
    divs[i * j].append(i)

To:

for j in xrange(i, n + 1, i):
    divs[j].append(i)

For n=100000, I go from 0.522774934769 to 0.47496509552. This difference is bigger when made to numDivisorSieve, but as I understand, you're looking for speedups in divisorSieve

StackExchange Code Review Q#18346, answer score: 2