wp231957,关于勾股数
由 a*a + b*b = c*c变形可得 a*a = (c-b) * (c+b)
因此遍历 c-b 就可以得到 b 和 c
比如 a=24
a*a = 576
576 可以是 8*72( 此时b=(72-8)/2,c=(72+8)/2 )
可以是 6*96( 此时b=(96-6)/2,c=(96+6)/2 )
可以是 4*144( 此时b=(144-4)/2,c=(144+4)/2 )
这个算法应该是最快的(当然,还可以继续优化,但主体算法不变)
程序代码:
#include <stdio.h> #include <time.h> #define N 10000 // 耗时0.140秒,总数12467 int main() { int avoid_optimization = 0; clock_t t0 = clock(); for( unsigned a=1; a<N; ++a ) { for( unsigned c_minus_b=a-1; c_minus_b>0; --c_minus_b ) { if( a*a % c_minus_b != 0 ) continue; unsigned c_plus_b = a*a/c_minus_b; if( c_plus_b%2 != c_minus_b%2 ) continue; unsigned b = (c_plus_b - c_minus_b)/2; unsigned c = (c_plus_b + c_minus_b)/2; if( a > b ) continue; if( c >= N ) break; ++avoid_optimization; //printf( "%2d^2 + %2d^2 = %2d^2\n", a, b, c ); } } printf( "time = %.3f\ncount = %d\n", (clock()-t0+0.0)/CLOCKS_PER_SEC, avoid_optimization ); return 0; }