本文共 1011 字，大约阅读时间需要 3 分钟。

描述

勾股数，是由三个正整数组成的数组；能符合勾股定理 aa + bb = c*c ， (a, b, c) 的正整数解。如果 (a, b, c) 是勾股数，它们的正整数倍数，也是勾股数。如果 (a, b, c) 互质，它们就称为素勾股数。给定正整数N，计算出小于或等于N的素勾股数个数。(0 < a <= b <= c <= N)

输入

正整数N

输出

小于或等于N的素勾股数个数(0 < a <= b <= c <= N)

输入样例 1  

10                                                                                                                                                                                                

输出样例 1

1

 扩展知识：

所谓勾股数，一般是指能够构成三条边的三个正整数(例如a,b,c)。

即a*a+b*b=c*c; a,b,c∈N

又由于，任何一个(a,b,c)内的三个数同时乘以一个n得到的新数(na,nb,nc)仍然是勾股数，所以一般我们要找的是a,b,c三者（他们的最大公因数是1）的勾股数，即素勾股数。

产生素勾股数的方式：

设m > n 、m 和n 均是正整数，

 

a = m^2 − n^2;

b = 2mn;

c = m^2+n^2;

 

若m 和n 是互质，而且m 和n 其中有一个是偶数，计算出来的 (a, b, c) 就是素勾股数。

并且能够找到所有的素勾股数  

实现代码：

import java.util.Scanner;public class Main {	public static void main(String[] args) {				Scanner in=new Scanner(System.in);		int n=in.nextInt();		int m=(int) Math.sqrt(n);		int a,b,c;		int count=0;		for(int i=1;i<=m;i++)		{			for(int j=i+1;j<=m;j+=2)			{				if(gcd(i,j)==1)  //i和j必须互质，即最大公因数为1				{					a=j*j-i*i;					b=2*i*j;					c=i*i+j*j;					if(c<=n)count++;				}			}		}		System.out.println(count);	}	private static int gcd(int a,int b)	{		if(b==0)return a;		else return gcd(b,a%b);	}}

转载地址：http://pszci.baihongyu.com/