三角数の約数の総数
http://projecteuler.net/index.php?section=problems&id=12
問題。
約数の総数が500を超える三角数で最小のものを求めよ。
結構手こずった。力技のコードだと計算が終わらなかったので。
約数の総数の導出をいじったら大分現実的な速さになったので、これでよしとする。
# -*- coding:utf-8 -*- from math import sqrt def TriNum(n): """ n番目の三角関数を返す """ return n*(n+1)/2 def CountDivisors(n): """ 自然数nの約数の総数を返す n>4 """ c = 2 # 約数総数の初期値, 1とnで2 m = int(sqrt(n)) if m*m == n: c += 1 # 約数はsqrt(n)を境にして対称に存在するので # まずsqrt(n)が約数かを調べる for i in xrange(2, m+1): if n%i == 0: c+=2 # 2〜sqrt(n)までのiについて約数かを調べる # 約数の場合はj=n/iが約数として存在することになるので # c+=2する return c def main(): for n in xrange(1000000): t = TriNum(n) if CountDivisors(t) >=500: return t if __name__ == "__main__": print main()
それにしてもxrangeとrangeってどっちが速いのか分からんときがある。