views:

411

answers:

1

I'm looking at ways to optimize my algorithm for solving Project Euler #75, two things I have done so far are,

  1. Only check L with even values as this can be easily proved.
  2. Store L values that have been verified to have only one way to form an integer sided right angle triangle. Later on, when checking a new L value, I look for L's divisors that are already verified to have this quality. If there are 2 or more divisors, then this value is skipped. E.g. 12, 30 and 40 are stored (24, 36, etc. are not stored because they are really enlarged versions of 12), so when I see 60 or 120, I can quickly determine that they should be skipped.

However my algorithm is still not quick enough. Do you have other suggestions or links to relevant articles? Thanks.

+2  A: 

http://en.wikipedia.org/wiki/Pythagorean%5Ftriple

and

http://en.wikipedia.org/wiki/Formulas%5Ffor%5Fgenerating%5FPythagorean%5Ftriples

EDIT

I just solved the problem, using one of this formulas, If you need extra hint just post comment

ralu
I abandoned my original approach and used Euclid's formula to generate Pythagorean triples and my program finished in a couple of seconds with correct result. Thanks.
grokus