勾股数元组 （C语言代码）

这一题的关键是，尽量减少循环层数。那就要根据数学关系，先尽可能地缩小变量的取值范围。

首先题目中有a < b < c;

2ab < a^2 + b^2 = c^2 <=M^2，推出b<M^2/(2*a) && b<M 。

2*a^2 < a^2 + b^2 = c^2 <=M^2, 推出a < (M/2)^0.5 && a < b 。

#include <stdio.h>
#include <stdlib.h>/*标准库头文件*/
#include <string.h>
#include <math.h>

int isHZ(int n1, int n2)/*判断两数是否互质*/
{
    int min , max;
    if(n1> n2)
    {
        min = n2;
        max = n1;
    }
    else
    {
        min = n1;
        max = n2;
    }
    if(min == 1) return 0;/*1本身非质非合，不与任何数互质*/
   int i;

   for(i=min;i>1;i--)/*从较小的那一个数开始往下找公约数*/
   {
       if(min%i == 0 && max%i == 0) return 0;
   }
   return 1;
}

int isHZ_3N(int n1, int n2, int n3)/*判断3个数是否两两互质*/
{
    if(isHZ(n1, n2) && isHZ(n1, n3) && isHZ(n2, n3))
        return 1;
    return 0;
}

int isPFS(int n)/*判断一个数是否为某个整数的平方*/
{
    double q = sqrt( (double) n);
    int n2 = (int) q;
    if( q == n2 ) return 1;
    return 0;
}
int main(void)
{
	int N, M;
    scanf("%d%d", &N, &M);
    int i, j, k, num = 0;
    if(N == 1) N = 2;
    for(i=N;i < M/sqrt(2);i++)
    {
        for(j=i+1;j<(M*M/i/2) && j<M;j++)
        {
            int l = i*i+j*j;
            if(isPFS(l) && l <= M*M )
            {
                k = (int) sqrt(l);
                if(isHZ_3N(i, j, k))
                {
                   printf("%d %d %d\n", i, j, k);
                   num ++;
                }
            }
        }
    }
    if(!num)
    {
        printf("NA");
    }
	return 0；
}