Consider the triangles with integer sides $a$, $b$ and $c$ with $a \leq b \leq c$. An integer sided triangle $(a,b,c)$ is called primitive if $\gcd(a,b,c)=1$. How many primitive integer-sided triangles exist with a perimeter not exceeding $10 000 000$?
I am trying to solve this on Euler project. I am wondering what is the best way to go to find the valid triples for constructing a triangle. Of course, you can do nested for loops but that is not efficient. Any pointers would help.
Thanks
On
There is a formula which gives you all the Pythagorean triples. That should cut down your search space a bit.
On
HINT $\rm\ gcd(a,b,c) = gcd(10^7-b-c,b,c) = gcd(10^7,b,c)\:, $ so a triple will be primitive unless $\rm\:b,c\:$ are both divisible by $2$ or $5$. The longest leg $\rm\:c\:$ must be less than half the perimeter $\rm\:P\:$ and at least $\rm\:P/3\:.\: $ Therefore, for each $\rm\:c\:$ in this range, count the values of $\rm\ b = c,\: c-1,\ldots, \lceil (P-c)/2\rceil\ $ such that $\rm\:b,c\:$ have neither $2$ nor $5$ as a common divisor. It depends only on $\rm\:b,c\:$ modulo $\ldots$
This is problem 276. I haven't solved it, but the first thing to realize is you don't have to loop over c-from a and b you should be able to find the number of solutions. Of course, you don't have time to loop over both a and b, but you may be able to loop over a. I would start by doing a brute force run up to 100 or 250-you should have time for that. Keep track of the number of solutions for each a. Then try to find a formula for the number of triangles that include a. This will probably be based on the factors of a.
Hope this helps. I did a lot of them, but have gotten less energetic now.