Project Euler その9

Problem11がどうにもうまくいかないので先に進む。

Problem12

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?

訳

三角数の数列は自然数を足していくことで表現される。なので7つ目の三角数は
1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 となる。
三角数の最初の10個は 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...のようになる。
最初の7つの三角数の因数をリストアップしてみよう。
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
28は5つ以上の除数を持つ最初の三角数だとわかる。
500個以上の除数を持つ最初の三角数の値はいくつか？

コード

from math import sqrt, ceil

def count_divisors(N):
    fact = 1
    j = 0
    max = ceil(sqrt(N))
    if N >= 3:
        while N!=1 and N%2==0:
            j += 1
            N /= 2
        i = 3
        fact *=(j+1)
        j = 0
        while N!=1 and i<=max:
            while N!=1 and N%i==0:
                j += 1
                N /= i
            fact *=(j+1)
            i += 2
            j = 0
        if N > max:
            fact *=2

    return fact

i = 0
j = 1
while 1:
    i += j
    j += 1
    if count_divisors(i) >= 500:
        print i
        break

素因数分解をまじめに書いたのでけっこう速い。