牛客刷题1-勾股元组数

题目-勾股元组数

如果三个正整数A、B、C ,A²+B²=C²则为勾股数

如果ABC之间两两互质，即A与B，A与C，B与C均互质没有公约数，则称其为勾股数元组。请求出给定n~m范围内所有的勾股数元组。

输入

起始范围

1 < n < 10000
n < m < 10000
1
2

输出

ABC保证A<B<C；输出格式A B C

多组勾股数元组，按照A B C升序的排序方式输出。

若给定范围内，找不到勾股数元组时，输出Na。

关键点

1. a b 互质，即 a 和 b 的公约数为1

概念：公约数只有1的两个数叫做互质数。根据互质数的概念可以对一组数是否互质进行判断。如：3和11的公约数只有1，则它们是互质数。

这里用阿基里德算法（辗转相除法），递归方式，如果最后结果==1，表示a,b 互质：gcd(a,b) = gcd(b, a%b)

2. i，j，k 用穷举法得出，满足条件 i<j<k，且 i,j,k 两两互质

两个数是否互质

def isPrime(x,y):
    """
    作用：
        判断两个数是否互质
    参数：
        提供两个数:x,y
    返回值：
        布尔值
    """
    if x == y and y == 1:
        return False

    min_ = min(x,y)

    for i in range(2, min_ + 1):
        if x % i == 0 and y % i == 0: # 余数为0，说明此时i就是二者的另一个公约数（且i>=2）
            return False
    else:
        return True

isPrime(1,1)

False

isPrime(2,9)

True

isPrime(3,8)

True

isPrime(3,15)

False

勾股元组数判断

def isPrime(x,y):
    """
    作用：
        判断两个数是否互质
    参数：
        提供两个数:x,y
    返回值：
        布尔值
    """
    if x == y and y == 1:
        return False

    min_ = min(x,y)

    for i in range(2, min_ + 1):
        # 余数为0，说明此时i就是二者的另一个公约数（且i>=2）
        if x % i == 0 and y % i == 0:
            return False
    else:
        return True  # for循环完之后没有满足的i，就说明二者是互质的-True


def gou_gu(m,n):
    flag = False
    for a in range(m, n-1):
        for b in range(a+1, n):
            for c in range(b+1, n+1):
                if isPrime(a,b) and isPrime(a,c) and isPrime(b,c) and a**2 + b**2 == c**2:
                    print(f"{a}\n{b}\n{c}")
                    print("*" * 10)
                    # 只要出现了勾股数，标志位变成True
                    flag = True

    if not flag:
        print("Na")

gou_gu(3,9)

3
4
5
**********

gou_gu(3,20)

3
4
5
**********
5
12
13
**********
8
15
17
**********

gou_gu(8,20)

8
15
17
**********

gou_gu(5,20)

5
12
13
**********
8
15
17
**********