Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
382 views
in Technique[技术] by (71.8m points)

triangle numbers in python

I'm trying to solve the problem:

What is the value of the first triangle number to have over five hundred divisors?

A triangle number is a number in the sequence of the sum of numbers i.e. 1+2+3+4+5...

I'm pretty sure that this is working code but I don't know because my computer is taking too long to calculate it. Does anybody have any idea of how to make the program a little faster.
Thanks.

import math

def main():
    l = []
    one = 0
    a = 1
    b = 2
    while one == 0:
        a = a + b 
        b += 1
        for x in range(1, int(a/2 + 1)):
            if a % x == 0:
                l.append(x)
                if len(l) > 499:
                    print a 

if __name__ == '__main__':
    main()
See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

Hints:

  • what is the formula for n-th triangular number?
  • n and n+1 have no common factors (except 1). Question: given number of factors in n and n+1 how to calculate number of factors in n*(n+1)? What about n/2 and (n+1) (or n and (n+1)/2)?
  • if you know all prime factors of n how to calculate number of divisors of n?

If you don't want to change your algorithm then you can make it faster by:

  • replace l.append by factor_count += 1
  • enumerate to int(a**.5) instead of a/2 (use factor_count += 2 in this case).

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...