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 functionif __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,000 | 21.2197508864    |  10.1484527586  5,000,000 | 27.1910144928    |  12.7670585308  6,000,000 | 33.6597508864    |  15.4226118057  7,000,000 | 39.7509513591    |  18.2902677738  8,000,000 | 46.5065447534    |  21.1247001928  9,000,000 | 53.2574136966    |  23.8988925173 10,000,000 | 60.0628718044    |  26.8588813211 11,000,000 | 66.0121182435    |  29.4509693973 12,000,000 |   MemoryError    |  32.3228102258 20,000,000 |   MemoryError    |  56.2527237669 30,000,000 |   MemoryError    |  86.8917332214 40,000,000 |   MemoryError    |  118.457179822 50,000,000 |   MemoryError    |  149.526622815 60,000,000 |   MemoryError    |  181.627320396 70,000,000 |   MemoryError    |  214.17467749 80,000,000 |   MemoryError    |  246.23677614 90,000,000 |   MemoryError    |  279.53308422100,000,000 |   MemoryError    |  314.813166014Results are pretty good and I'm happy I was able to get it this far, but I'm looking to get it even faster. If at all possible, I'd like to get 100,000,000 at a reasonable speed with the divisorSieve. Although this also brings into the issue that anything over 12,000,000+ throws a MemoryError at divs = [[1] for x in xrange(0, n + 1)]) in divisorSieve. numDivisorSieve does allow the full 100,000,000 to run. If you could also help get past the memory error, that would be great.I've tried replacing numDivisorSieve's divs = [1] * (n + 1) with both divs = array.array('i', [1] * (n + 1)) and divs = numpy.ones((n + 1), dtype='int') but both resulted in a loss of speed (slight difference for array, much larger difference for numpy). I expect that since numDivisorSieve had a loss in efficiency, then so would divisorSieve. Of course there's always the chance I'm using one or both of these incorrectly since I'm not used to either of them.I would appreciate any help you can give me. I hope I have provided enough details. Thank you.
Optimizing Divisor Sieve
python;optimization