Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


share|cite|improve this question

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.

share|cite|improve this answer

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$

share|cite|improve this answer
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

There is a formula which gives you all the Pythagorean triples. That should cut down your search space a bit.

share|cite|improve this answer
The triangles need not be right-angled. – Chris Eagle Jan 5 '11 at 16:39

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.