# Primitive integer triangles

Consider the triangles with integer sides a, b and c with a ≤ b ≤ 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

-

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.

-

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$

-
The perimeter need not be $=10^7$, it just has to be $\leq 10^7$ –  Ross Millikan Jan 5 '11 at 21:35
Indeed, but once should able to use similar sieve-like ideas to avoid gcd computations. But there is probably a better way. –  Bill Dubuque Jan 5 '11 at 22:06
Does it mean that the solution wont work for p <= 10^7? –  Jinesh Parekh Jan 6 '11 at 6:07