optimization help to find max number of divisors

Question

I'm trying to solve problem 12 of Euler project. What is the value of the first triangle number to have over five hundred divisors? ( the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28). This is my code, but it is not fast enough.. Do you have any optimization tips?

n=0
a=0
list=[]
maxcount=0


while True:
    n+=1
    a+=n
    count=0
    for x in range(1,int(a+1)):
        if a%x==0:
            count+=1   
            if count>maxcount:
                maxcount=count
                print a, "has", maxcount, "dividors"

Thank you!

only check divisors up to the sqrt of the number. Saves millions of checks — Justin, Apr 14 '13 at 05:54

score 1 · Answer 1 · edited May 23 '17 at 12:04

Grab the code from this question which implements very fast prime factorization:
Fast prime factorization module

Then use the answer to this question to convert your prime factors into a list of all divisors (the length is what you want):
What is the best way to get all the divisors of a number?

For example, you can add the following function (adapted from the second link) to the bottom of the module from the first link:

def alldivisors(n):
    factors = list(factorization(n).items())
    nfactors = len(factors)
    f = [0] * nfactors
    while True:
        yield reduce(lambda x, y: x*y, [factors[x][0]**f[x] for x in range(nfactors)], 1)
        i = 0
        while True:
            if i >= nfactors:
                return
            f[i] += 1
            if f[i] <= factors[i][1]:
                break
            f[i] = 0
            i += 1

Then in your code to count divisors you would use len(list(alldivisors(a))) which will calculate the number of divisors significantly more quickly than the brute force method you are currently using.

score 1 · Accepted Answer · answered Apr 12 '13 at 16:33

1

Start with reducing the search space, no need to look at numbers that are not triangle numbers. Also try looking at divisors in range(1, sqrt(n)) instead of range(1, n)

answered Apr 12 '13 at 16:33

Stedy

7,359
14
57
77

score 0 · Answer 3 · answered Apr 12 '13 at 16:30

Apart from number theory: try caching, and doing things the other way around. For example: When you already know that 300 has 18 divisors (and what they are), what does that mean for a number which is dividable by 300? Can you cache such information? (sure you can.)

Pure python speedup hacks won't help you, you need a better algorithm.

optimization help to find max number of divisors

3 Answers3