0
\$\begingroup\$

I'm new to python and programming in general and I found Project Euler problems a good way to practice python. But my code is pretty slow. It seems to work, didn't wait long enough for the code to print the answer though. Any tips on how to make it faster ? I assume that you don't have to check every single number but that's just a guess any help appreciated.

tri_nums = [1]
divisors = []
temp_divisors =[]

while len(divisors) <= 500:
    for x in range(1, tri_nums[-1] + 1):
        if tri_nums[-1] % x == 0:
            temp_divisors.append(x)
    if len(temp_divisors) > len(divisors):
        divisors = temp_divisors[:]
    temp_divisors.clear()

    print("Number: " + str(tri_nums[-1]))
    print("Number of divisors: " + str(len(divisors)))
    print("List of divisors: " + str(divisors))
    tri_nums.append(len(tri_nums) + 1 + tri_nums[-1])
\$\endgroup\$
  • 1
    \$\begingroup\$ You only need to check for divisors up to the square root of the number \$\endgroup\$ – juvian Aug 27 '18 at 18:11
  • \$\begingroup\$ i see and then it gives me half of the divisors, could you explain a math behind this (i feel really stupid rn) \$\endgroup\$ – RKJ Aug 27 '18 at 18:18
  • \$\begingroup\$ It´s half, but you can get its pairs doing n / that divisor. Here is an explanation \$\endgroup\$ – juvian Aug 27 '18 at 18:19
  • \$\begingroup\$ "didn't wait long enough for the code to print the answer though." Why not? Don't you want to know whether it works for sure? \$\endgroup\$ – Mast Aug 27 '18 at 18:33
  • \$\begingroup\$ @Mast in this case, that would take hours if not days \$\endgroup\$ – juvian Aug 27 '18 at 18:38
5
\$\begingroup\$

To avoid spoiling the problem for you, I'll offer some hints.

Hint 1:

Have you read the Wikipedia article about the triangular numbers? It's always worth doing a bit of research into the mathematical background of a Project Euler problem.

Hint 2:

There is a mathematical formula for the \$n\$th triangular number, namely \${1\over2}n(n+1)\$.

Hint 3:

What do you know about the divisors of \${1\over2}n(n+1)\$? Try out some small examples and see if there is a pattern.

Hint 4:

When a problem requires you to establish some facts about the divisors of all the numbers in a range, then what you need is a sieve.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.