Project Euler, Problem #12, Python

# The sequence of triangle numbers is generated by adding the natural
# numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 +
# 7 = 28. The first ten terms would be: 1, 3, 6, 10, 15, 21, 28, 36,
# 45, 55, ... Let us list the factors of the first seven triangle
# numbers: 1: 1; 3: 1, 3; 6: 1, 2, 3, 6; 10: 1, 2, 5, 10; 15: 1, 3, 5,
# 15; 21: 1, 3, 7, 21; 28: 1, 2, 4, 7, 14, 28 We can see that 28 is
# the first triangle number to have over five divisors. What is the
# value of the first triangle number to have over five hundred
# divisors?

# Version 1: slightly shorter and faster

cntr = 2
ctn = 1
dn = 0

while True:
    ctn += cntr
    md = int(ctn ** 0.5)
    if md < ctn ** 0.5:
        cv = 0
    else:
        cv = 1

    if ctn % 2 == 0:
        dn = sum([2 if ctn % x == 0 else 0 for x in range(1, md + 1)])

    else:
        dn = sum([2 if ctn % x == 0 else 0 for x in range(1, md + 1, 2)])

    if dn - cv > 500:
        break
    dn = 0
    cntr += 1

print(ctn)

# 76576500
# 24752 function calls in 9.839 seconds

# Version 2

cntr = 2
ctn = 1
dn = 0

while True:
    ctn += cntr
    md = int(ctn ** 0.5)
    if md < ctn ** 0.5:
        cv = 0
    else:
        cv = 1

    if ctn % 2 == 0:
        for d in range(1, md + 1):
            if ctn % d == 0:
                dn += 2
    else:
        for d in range(1, md + 1, 2):
            if ctn % d == 0:
                dn += 2

    if dn - cv > 500:
        break
    dn = 0
    cntr += 1

print(ctn)

# 76576500
# 12376 function calls in 10.944 seconds