Help us understand the problem. What is going on with this article?

Project Euler 9 演算結果の保持

More than 5 years have passed since last update.

ピタゴラス数(ピタゴラスの定理を満たす自然数)とは a < b < c で以下の式を満たす数の組である.

a2 + b2 = c2
例えば, 32 + 42 = 9 + 16 = 25 = 52 である.

a + b + c = 1000 となるピタゴラスの三つ組が一つだけ存在する.
これらの積 abc を計算しなさい.
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%209

まずは素直に書いてみた。

def cof1():
  target=1000
  (a,b,c) = (1, 1, target - 2)
  ans = 0
  while a < c:
    while b < c:
      if a**2 + b**2 == c**2:
        ans = a*b*c
        break
      (b,c) = (b + 1, c - 1)
    if ans:
      break
    else:
      (a,b,c) = (a + 1, a + 1, target - a*2 -2)
  #print ans

再度見直して、毎回a,b,cの2乗を計算するのは非効率な気がした。
pe9.png

ということで予め1から999それぞれの二乗のlistを作成して、それを参照するようにしてみた。

def cof2():
  target=1000
  sq = [x**2 for x in range(0,target)] #create 
  (a,b,c) = (1, 1, target - 2)
  ans = 0
  while a < c:
    while b < c:
      if sq[a] + sq[b] == sq[c]:
        ans = a*b*c
        break
      (b,c) = (b + 1, c - 1)
    if ans:
      break
    else:
      (a,b,c) = (a + 1, a + 1, target - a*2 -2)
  #print ans

結果、1回あたり3.9ミリ秒(下記は100回実行)を削減できた。

pe9_2.png

cof
特許弁理士です。仕事ではプログラムを書いていませんが、日曜プログラマになれるよう、Project Eulerでもやりながら研鑽していこうかと考えています。 pythonを学習中です。いろいろご指摘いただけますと幸いです。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away