Euler Problem No. 276 - Primitive Triangles

Question

I tried to solve the problem problem No. 276 from Project Euler , but so far failed.

Consider triangles with integers on the sides a, b, and c with ≤ b ≤ c. an integer triangle (a, b, c) is equal to a called primitive if gcd (a, b, c) = 1. How many primitive integer triangles exist with a perimeter not exceeding 10,000,000?

The bottleneck in my code is function GCD. For my sample input, almost 90% of the lead time. I would like to hear tips, comments on how to improve the solution ... My solution is written in C, but it is just simple:

#include <stdio.h>
#include <math.h>

#define sides 3
// This is where my program spends most of its time
size_t bi_gcd (size_t a, size_t b);
size_t tri_gcd (size_t a, size_t b, size_t c);
size_t count_primitive_triangles (size_t maximum_perimeter);

int main()
{
 printf( "primitive_triangles = %lu \n",
            count_primitive_triangles(1000) );
}

size_t bi_gcd (size_t a, size_t b)
{
 size_t t;

 while(b != 0)
 {
  t = b;
  b = a % b;
  a = t;
 }

 return a;
}

size_t tri_gcd (size_t a, size_t b, size_t c)
{
 return bi_gcd(a, bi_gcd(b, c));
}

size_t count_primitive_triangles (size_t max_perimeter)
{
 size_t count = 0; // number of primitive triangles
 size_t a, b, c;   // sides of the triangle
 // the following are the bounds of each side
 size_t 
  // because b >= a && c >= b ==> max of a
  // is when a+b+c > 10,000,000
  // b == a (at least)
  // c == b (at least)
  // ==> a+b+c >= 10,000,000
  // ==> 3*a   >= 10,000,000
  // ==> a= 10,000,000/3
  a_limit = max_perimeter/sides,
  b_limit,
  c_limit;

 for (a = 1; a <= a_limit; ++a)
 {
  // because c >= b && a+b+c <= 10,000,000
  // ==> 2*b + a = 10,000,000
  // ==> 2*b = 10,000,000 - a
  // ==> b = (10,000,000 - a)/2
  for (b = a, b_limit = (max_perimeter-a)/2; b <= b_limit; ++b)
  {
   // The triangle inequality:
   // a+b > c (for a triangle to be valid!)
   // ==> c < a+b
   for (c = b, c_limit = a+b; c < c_limit; ++c)
   {
    if (tri_gcd(a, b, c) == 1)
     ++count;
   }
  }
 }

 return count;
}

Answer 1

, , , gcd , ( ) , .:-) - , , .

. : ( ) a + b + c = n? ( O (n) - Ω (n ³).) , ? , p, ? (: a + b + c = n <= > (a/p) + (b/p) + (c/p) = n/p.) .

. Project Euler, , , , . ( , , , ), / :

• , 1 ≤ a ≤ b ≤ c, a + b + c = n. p = b + c-a = n-2a, q = c + a-b = n-2b, r = a + b-c = n-2c. 1 ≤ r ≤ q ≤ p p + q + r = a + b + c = n. , p, q, r n.
• , 1 ≤ r ≤ q ≤ p p + q + r = n, ( n), a = (q + r)/2, b = (r + p)/2, c = (p + q)/2. 1 ≤ a ≤ b ≤ c a + b + c = n. , ().
• , (a, b, c) n n (p, q, r) . .

, T (n) T (n-k), .

(, , , Google, ?)

Answer 2

, :

• tri_gcd(a,b,c) g1 = gcd(a,b) g2 = gcd(g1, c) .

• gcd(a,b)==1, max_c - min_c + 1, , gcd 1 c.

• , , a+b+c <= 10000000.

, , , , , . , , - .

Answer 3

, , :)

:

• 2..10 ⁷ .
• bi_gcd(a, b) , a b return 1 gcd.
  tri_gcd(a, b, c).

: @interjay:

, , a - , , b a,
- (b % a == 0). a gcd.

Answer 4

Nick D, , bi_gcd, , , bi_gcd () . GCD (12, 18) 6, , . , .

Answer 5

, .

size_t bi_gcd (size_t a, size_t b) {
    if (a == 1 || b == 1) return 1;
    ...

size_t tri_gcd (size_t a, size_t b, size_t c) {
    if (a%2==0 && b%2==0 && c%2==0) return 2;
    // of course GCD(a,b,c) can be > 2,
    // but the exact GCD is not needed in this problem.
    ...

With these two if-s, I can shorten the time from 1.2 seconds to 1.0 seconds (with gcc -O3).