Project Euler 9 Retention of calculation results

A Pythagorean triple (a natural number that satisfies the Pythagorean theorem) is a set of numbers that satisfy the following equation with a <b <c.

a2 + b2 = c2 For example, 32 + 42 = 9 + 16 = 25 = 52.

There is only one Pythagoras triplet with a + b + c = 1000. Calculate the product abc of these. http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%209

First of all, I wrote it obediently.

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

I felt that it would be inefficient to review it again and calculate the squares of a, b, and c each time. pe9.png

So I created a list of squares from 1 to 999 in advance and tried to refer to it.

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

As a result, we were able to reduce 3.9 milliseconds per time (the following is executed 100 times).

pe9_2.png

Recommended Posts

Project Euler 9 Retention of calculation results
Project Euler 37
Project Euler 7
Project Euler 47
Project Euler 10 "Sum of Prime Numbers"
Project Euler 31
Project Euler 4
Project Euler 38
Project Euler 17
Project Euler 26
Project Euler 23
Project Euler 22
Project Euler 19
Project Euler 50
Project Euler 42
Project Euler 33
Project Euler 32
Project Euler 43
Project Euler 36
Project Euler 24
Project Euler 46
Project Euler 48
Project Euler 45
Project Euler 6
Project Euler 39
Project Euler 49
Project Euler 29
Project Euler 27
Project Euler 41
Project Euler 30
Project Euler 16
Project Euler 14
Project Euler 34
Project Euler 25
Project Euler # 16 "Sum of Powers" in Python
Project Euler # 17 "Number of Characters" in Python
Project Euler # 1 "Multiples of 3 and 5" in Python
[Project Euler] problem1
Project Euler # 10 "sum of prime numbers" in Python
Project Euler # 13 "Sum of Large Numbers" in Python
Project Euler # 6 "Difference in sum of squares" in Python
Project Euler15 "Lattice Path"
Project Euler 2 Acceleration 2.21 Save microseconds.
Project Euler Original Method Group 1
Reuse the results of clustering
Calculation of similarity by MinHash
About cost calculation of MeCab
What is Project Euler 3 Acceleration?