华为机试练习（四）勾股数元组

题目描述 给定正整数N， 计算出小于或等于N的素勾股数个数 关于素勾股数，简单来说，就是 a 2 + b 2 = c 2 且 a、b、c 互质，则称（a，b，c）为一组素勾股数

【分析】 可以通过三层循环，找到所有符合要求的数，得到其个数，不过这样当 N 大些的时候效率就比较低； 了解（素勾股数、毕达哥拉斯三元组等知识），可得到关于素勾股数的一个结论： 对于一组素勾股数（a，b，c），存在 m、n 使得 a = m 2 - n 2，b = 2mn， c = m 2 + n 2，且 gcd(m,n) = 1 由此可将三层循环化为两层循环

【实现】

// 获取输入
const input = 1000
let res = 0
// c=m^2 + n^2，又m、n都大于0，所以它们一定不超过c的开方
const len = Math.ceil(Math.sqrt(input))

for (let i = 1; i < len; i++) {
          
   
    for (let j = i + 1; j < len; j++) {
          
   
    	// m、n不互质，跳过
    	if(isCoprime(i, j) !== 1) continue
    	
        let a = Math.pow(j, 2) - Math.pow(i, 2)
        let b = 2 * i * j
        let c = Math.pow(j, 2) + Math.pow(i, 2)
        if (c <= input) {
          
   
        	// 当前勾股数数不超过给定值
            if ((isCoprime(a, b) === 1) && (isCoprime(a, c) === 1) && (isCoprime(b, c) === 1)) {
          
   
            	// 勾股数两两互质
                res++
            }
        }
    }
}

// 判断两个数是否互质：最大公因数是否为1
function isCoprime(x, y) {
          
   
    // 不必考虑 x、y 的大小 第一次递归之后大的总会在前面
    if (y === 0) {
          
   
        return x
    } else {
          
   
        return isCoprime(y, x % y)
    }
}

// 输出
console.log(res);