Skip to main content
Code Review

Return to Question

Rollback to Revision 1
Source Link
Jamal
Jamal
  • 35.2k
  • 13
  • 134
  • 238

Update: The optimizations so far have been excellent. And I've used Python 64 bit to get around the memory issue, but I came to the problem that 50,000,000+ causes my computer to use up more than it's 8 gigs of memory and freeze. I've update the times for 20,00,000 to 40,000,000 for divisorSieve. 40,000,000 capped out at just over 7 gigs of memory. So something will have to be done, perhaps by writing to file or serializing part of the array, to free up memory.

I've never run into this issue before so suggestions are welcome. I'll also be looking into this on my own so if I come up with something, I will update again. I really thank people for their help so far!

Original Post (just with results and code updated): 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.

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, i): divs[j]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, i): divs[j]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) 
 -----n-----|--time(divSieve)--|--time(numDivSieve)-- 100,000 |  0.118300055981 333831560615 |  0.0687864651365187762331281 200,000 |  0.19642657212271700566026 |  0.133795795235362314797537 300,000 | 0 1.2794828015181643773714  |  0.2090971574355124339118 400,000 | 0 1.37709491820663861821235 |  0.273495055048748340797412 500,000 | 0.52753871991 2.06917832929 |  0.33962928407959312993718 600,000 | 0 2.56667506375652753840891 | 0 1.40610250668717777010636 700,000 | 0 3.68520401816301465945139 | 0 1.47162219319538268800149 800,000 | 0 3.75536356285449267338434 | 0 1.53857560490162560614543 900,000 | 0.85135473036 3.98145114138 | 0 1.62032624245883002270324 1,000,000 | 0 4.9628313740134809342539  | 0 2.67567363314110247496423 2,000,000 | 19.9085028301380035361075 | 1 4.3477209678459150618897 3,000,000 | 215.83754773901465184114  | 2 7.0388760340924799900479 4,000,000 | 321.818084219692197508864 | 2 10.716361261431484527586 5,000,000 | 427.775635379741910144928 | 3 12.36783977117670585308 6,000,000 | 533.713483547936597508864 | 4 15.04204671274226118057 7,000,000 | 639.643012999947509513591 | 4 18.719181439322902677738 8,000,000 | 746.625172917835065447534 | 5 21.389290912481247001928 9,000,000 | 853.605791192392574136966 | 6 23.069122037698988925173 10,000,000 | 960.575549853830628718044 | 6 26.766407911928588813211 2011,000,000 | 1666.2312259750121182435  | 29.4509693973  12,000,000 | 13 MemoryError | 32.48032002243228102258  3020,000,000 | 24 MemoryError | 56.25937799342527237669 30,000,000 |  MemoryError  | 2086.30578497238917332214 40,000,000 | 32.8265861168 MemoryError  | 27118.0092311999457179822 50,000,000 | Out of MemoryMemoryError | 33149.7464085339526622815 60,000,000 | Out of MemoryMemoryError | 40181.5103277975627320396 70,000,000 | Out of MemoryMemoryError | 47214.252135037617467749 80,000,000 | Out of MemoryMemoryError | 54246.179025315723677614 90,000,000 | Out of MemoryMemoryError | 60279.71678982453308422 100,000,000 | Out of MemoryMemoryError | 67314.4218930771813166014

Results 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 1912,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.

Update: The optimizations so far have been excellent. And I've used Python 64 bit to get around the memory issue, but I came to the problem that 50,000,000+ causes my computer to use up more than it's 8 gigs of memory and freeze. I've update the times for 20,00,000 to 40,000,000 for divisorSieve. 40,000,000 capped out at just over 7 gigs of memory. So something will have to be done, perhaps by writing to file or serializing part of the array, to free up memory.

I've never run into this issue before so suggestions are welcome. I'll also be looking into this on my own so if I come up with something, I will update again. I really thank people for their help so far!

Original Post (just with results and code updated): 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.

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, i): divs[j].append(i) 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, i): divs[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) 
 -----n-----|--time(divSieve)--|--time(numDivSieve)-- 100,000 | 0.118300055981  | 0.0687864651365 200,000 | 0.196426572122 | 0.133795795235 300,000 | 0.279482801518 | 0.20909715743 400,000 | 0.377094918206 | 0.273495055048 500,000 | 0.52753871991 | 0.33962928407 600,000 | 0.566675063756 | 0.406102506687 700,000 | 0.685204018163 | 0.471622193195 800,000 | 0.755363562854 | 0.538575604901 900,000 | 0.85135473036 | 0.620326242458 1,000,000 | 0.962831374013 | 0.675673633141 2,000,000 | 1.90850283013 | 1.34772096784 3,000,000 | 2.83754773901 | 2.03887603409 4,000,000 | 3.81808421969 | 2.71636126143 5,000,000 | 4.77563537974 | 3.3678397711 6,000,000 | 5.71348354793 | 4.0420467127 7,000,000 | 6.64301299994 | 4.71918143932 8,000,000 | 7.62517291783 | 5.38929091248 9,000,000 | 8.60579119239 | 6.06912203769 10,000,000 | 9.57554985383 | 6.76640791192 20,000,000 | 16.231225975 | 13.4803200224 30,000,000 | 24.2593779934 | 20.3057849723 40,000,000 | 32.8265861168 | 27.0092311999 50,000,000 | Out of Memory | 33.7464085339 60,000,000 | Out of Memory | 40.5103277975 70,000,000 | Out of Memory | 47.2521350376 80,000,000 | Out of Memory | 54.1790253157 90,000,000 | Out of Memory | 60.716789824 100,000,000 | Out of Memory | 67.4218930771

Results 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 19,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 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.

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) 
 -----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.53308422 100,000,000 | MemoryError | 314.813166014

Results 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.

Updated with results from trying Python 64 bit
Source Link
Jeremy K
Jeremy K
  • 241
  • 1
  • 5

Update: The optimizations so far have been excellent. And I've used Python 64 bit to get around the memory issue, but I came to the problem that 50,000,000+ causes my computer to use up more than it's 8 gigs of memory and freeze. I've update the times for 20,00,000 to 40,000,000 for divisorSieve. 40,000,000 capped out at just over 7 gigs of memory. So something will have to be done, perhaps by writing to file or serializing part of the array, to free up memory.

I've never run into this issue before so suggestions are welcome. I'll also be looking into this on my own so if I come up with something, I will update again. I really thank people for their help so far!

Original Post (just with results and code updated): 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.

 -----n-----|--time(divSieve)--|--time(numDivSieve)-- 100,000 | 0.118300055981  | 0.0687864651365 200,000 | 0.196426572122  | 0.133795795235 300,000 | 0.279482801518  | 0.20909715743 400,000 | 0.377094918206  | 0.273495055048 500,000 | 0.52753871991  | 0.33962928407 600,000 | 0.566675063756  | 0.406102506687 700,000 | 0.685204018163  | 0.471622193195 800,000 | 0.755363562854  | 0.538575604901 900,000 | 0.85135473036  | 0.620326242458 1,000,000 | 0.962831374013  | 0.675673633141 2,000,000 | 1.90850283013  | 1.34772096784 3,000,000 | 2.83754773901  | 2.03887603409 4,000,000 | 3.81808421969  | 2.71636126143 5,000,000 | 4.77563537974  | 3.3678397711 6,000,000 | 5.71348354793  | 4.0420467127 7,000,000 | 6.64301299994  | 4.71918143932 8,000,000 | 7.62517291783  | 5.38929091248 9,000,000 | 8.60579119239  | 6.06912203769 10,000,000 | 9.57554985383  | 6.76640791192 20,000,000 |  16.231225975 MemoryError | 13.4803200224 30,000,000 |  MemoryError24.2593779934 | 20.3057849723 40,000,000 |  MemoryError32.8265861168 | 27.0092311999 50,000,000 | Out of MemoryErrorMemory | 33.7464085339 60,000,000 | Out of MemoryErrorMemory | 40.5103277975 70,000,000 | Out of MemoryErrorMemory | 47.2521350376 80,000,000 | Out of MemoryErrorMemory | 54.1790253157 90,000,000 | Out of MemoryErrorMemory | 60.716789824 100,000,000 | Out of MemoryErrorMemory | 67.4218930771

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.

 -----n-----|--time(divSieve)--|--time(numDivSieve)-- 100,000 | 0.118300055981 | 0.0687864651365 200,000 | 0.196426572122 | 0.133795795235 300,000 | 0.279482801518 | 0.20909715743 400,000 | 0.377094918206 | 0.273495055048 500,000 | 0.52753871991 | 0.33962928407 600,000 | 0.566675063756 | 0.406102506687 700,000 | 0.685204018163 | 0.471622193195 800,000 | 0.755363562854 | 0.538575604901 900,000 | 0.85135473036 | 0.620326242458 1,000,000 | 0.962831374013 | 0.675673633141 2,000,000 | 1.90850283013 | 1.34772096784 3,000,000 | 2.83754773901 | 2.03887603409 4,000,000 | 3.81808421969 | 2.71636126143 5,000,000 | 4.77563537974 | 3.3678397711 6,000,000 | 5.71348354793 | 4.0420467127 7,000,000 | 6.64301299994 | 4.71918143932 8,000,000 | 7.62517291783 | 5.38929091248 9,000,000 | 8.60579119239 | 6.06912203769 10,000,000 | 9.57554985383 | 6.76640791192 20,000,000 |  MemoryError | 13.4803200224 30,000,000 |  MemoryError | 20.3057849723 40,000,000 |  MemoryError | 27.0092311999 50,000,000 | MemoryError | 33.7464085339 60,000,000 | MemoryError | 40.5103277975 70,000,000 | MemoryError | 47.2521350376 80,000,000 | MemoryError | 54.1790253157 90,000,000 | MemoryError | 60.716789824 100,000,000 | MemoryError | 67.4218930771

Update: The optimizations so far have been excellent. And I've used Python 64 bit to get around the memory issue, but I came to the problem that 50,000,000+ causes my computer to use up more than it's 8 gigs of memory and freeze. I've update the times for 20,00,000 to 40,000,000 for divisorSieve. 40,000,000 capped out at just over 7 gigs of memory. So something will have to be done, perhaps by writing to file or serializing part of the array, to free up memory.

I've never run into this issue before so suggestions are welcome. I'll also be looking into this on my own so if I come up with something, I will update again. I really thank people for their help so far!

Original Post (just with results and code updated): 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.

 -----n-----|--time(divSieve)--|--time(numDivSieve)-- 100,000 | 0.118300055981  | 0.0687864651365 200,000 | 0.196426572122  | 0.133795795235 300,000 | 0.279482801518  | 0.20909715743 400,000 | 0.377094918206  | 0.273495055048 500,000 | 0.52753871991  | 0.33962928407 600,000 | 0.566675063756  | 0.406102506687 700,000 | 0.685204018163  | 0.471622193195 800,000 | 0.755363562854  | 0.538575604901 900,000 | 0.85135473036  | 0.620326242458 1,000,000 | 0.962831374013  | 0.675673633141 2,000,000 | 1.90850283013  | 1.34772096784 3,000,000 | 2.83754773901  | 2.03887603409 4,000,000 | 3.81808421969  | 2.71636126143 5,000,000 | 4.77563537974  | 3.3678397711 6,000,000 | 5.71348354793  | 4.0420467127 7,000,000 | 6.64301299994  | 4.71918143932 8,000,000 | 7.62517291783  | 5.38929091248 9,000,000 | 8.60579119239  | 6.06912203769 10,000,000 | 9.57554985383  | 6.76640791192 20,000,000 | 16.231225975 | 13.4803200224 30,000,000 | 24.2593779934 | 20.3057849723 40,000,000 | 32.8265861168 | 27.0092311999 50,000,000 | Out of Memory | 33.7464085339 60,000,000 | Out of Memory | 40.5103277975 70,000,000 | Out of Memory | 47.2521350376 80,000,000 | Out of Memory | 54.1790253157 90,000,000 | Out of Memory | 60.716789824 100,000,000 | Out of Memory | 67.4218930771
Added Adam Wagner's optimization and updated times as well as the point at which divisorSieve throws MemoryError which has also improved. Memory is more of an issue than speed at this point but speed increases are still welcome.
Source Link
Jeremy K
Jeremy K
  • 241
  • 1
  • 5
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, i): divs[i * j]divs[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, i):   divs[i * j]divs[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) 
 -----n-----|--time(divSieve)--|--time(numDivSieve)-- 100,000 |  0.333831560615 118300055981 |  0.1877623312810687864651365 200,000 |  0.71700566026 196426572122 |  0.362314797537133795795235 300,000 |  10.1643773714 279482801518 |  0.5512433911820909715743 400,000 |  10.63861821235 377094918206 |  0.748340797412273495055048 500,000 |  20.06917832929 52753871991 |  0.95931299371833962928407 600,000 |  20.52753840891 566675063756 |  10.17777010636406102506687 700,000 |  30.01465945139 685204018163 |  10.38268800149471622193195 800,000 |  30.49267338434 755363562854 |  10.62560614543538575604901 900,000 |  30.98145114138 85135473036 |  10.83002270324620326242458 1,000,000 |  40.4809342539 962831374013 |  20.10247496423675673633141 2,000,000 | 91.80035361075 90850283013 |  41.5915061889734772096784 3,000,000 | 152.465184114 83754773901 |  72.2479990047903887603409 4,000,000 | 213.2197508864 81808421969 |  102.148452758671636126143 5,000,000 | 274.1910144928 77563537974 |  123.76705853083678397711 6,000,000 | 335.6597508864 71348354793 |  154.42261180570420467127 7,000,000 | 396.7509513591 64301299994 |  184.290267773871918143932 8,000,000 | 467.5065447534 62517291783 |  215.124700192838929091248 9,000,000 | 538.2574136966 60579119239 |  236.898892517306912203769 10,000,000 | 60.0628718044  | 26.8588813211  11,000,000 | 66.0121182435 | 299.4509693973 12,000,000 | MemoryError 57554985383 |  326.3228102258 76640791192 20,000,000 | MemoryError | 5613.25272376694803200224 30,000,000 | MemoryError | 8620.89173322143057849723 40,000,000 | MemoryError | 11827.4571798220092311999 50,000,000 | MemoryError | 14933.5266228157464085339 60,000,000 | MemoryError | 18140.6273203965103277975 70,000,000 | MemoryError | 21447.174677492521350376 80,000,000 | MemoryError | 24654.236776141790253157 90,000,000 | MemoryError | 27960.53308422716789824 100,000,000 | MemoryError | 31467.8131660144218930771

Results 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 1219,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.

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) 
 -----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.53308422 100,000,000 | MemoryError | 314.813166014

Results 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.

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, i): divs[j].append(i) 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, i): divs[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) 
 -----n-----|--time(divSieve)--|--time(numDivSieve)-- 100,000 | 0.118300055981 | 0.0687864651365 200,000 | 0.196426572122 | 0.133795795235 300,000 | 0.279482801518 | 0.20909715743 400,000 | 0.377094918206 | 0.273495055048 500,000 | 0.52753871991 | 0.33962928407 600,000 | 0.566675063756 | 0.406102506687 700,000 | 0.685204018163 | 0.471622193195 800,000 | 0.755363562854 | 0.538575604901 900,000 | 0.85135473036 | 0.620326242458 1,000,000 | 0.962831374013 | 0.675673633141 2,000,000 | 1.90850283013 | 1.34772096784 3,000,000 | 2.83754773901 | 2.03887603409 4,000,000 | 3.81808421969 | 2.71636126143 5,000,000 | 4.77563537974 | 3.3678397711 6,000,000 | 5.71348354793 | 4.0420467127 7,000,000 | 6.64301299994 | 4.71918143932 8,000,000 | 7.62517291783 | 5.38929091248 9,000,000 | 8.60579119239 | 6.06912203769 10,000,000 | 9.57554985383 | 6.76640791192 20,000,000 | MemoryError | 13.4803200224 30,000,000 | MemoryError | 20.3057849723 40,000,000 | MemoryError | 27.0092311999 50,000,000 | MemoryError | 33.7464085339 60,000,000 | MemoryError | 40.5103277975 70,000,000 | MemoryError | 47.2521350376 80,000,000 | MemoryError | 54.1790253157 90,000,000 | MemoryError | 60.716789824 100,000,000 | MemoryError | 67.4218930771

Results 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 19,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.

Tweeted twitter.com/#!/StackCodeReview/status/266990352962039808
Source Link
Jeremy K
Jeremy K
  • 241
  • 1
  • 5