Я пытался решить проблему # 276 из Project Euler , но пока безуспешно.
Рассмотрим треугольники с целым числом
стороны a, b и c с a ≤ b ≤ c.
Целочисленный треугольник (a, b, c)
называется примитивным, если gcd (a, b, c) = 1. Как
много примитивных треугольников с целыми сторонами
существуют с периметром, не превышающим
10 000 000?
Узким местом в моем коде является функция GCD. Это почти занимает 90% времени выполнения для моего образца ввода. Я хотел бы услышать подсказки, комментарии о том, как улучшить решение ... Мое решение написано на C, но оно довольно простое:
#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;
}