牛客刷题1-勾股元组数

2023-08-25 11:37:41 浏览数 (2)

题目-勾股元组数

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

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

输入

起始范围

代码语言：javascript复制
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)

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

两个数是否互质

代码语言：javascript复制
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
代码语言：javascript复制
isPrime(1,1)
代码语言：javascript复制
False
代码语言：javascript复制
isPrime(2,9)
代码语言：javascript复制
True
代码语言：javascript复制
isPrime(3,8)
代码语言：javascript复制
True
代码语言：javascript复制
isPrime(3,15)
代码语言：javascript复制
False

勾股元组数判断

代码语言：javascript复制
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")
代码语言：javascript复制
gou_gu(3,9)
代码语言：javascript复制
3
4
5
**********
代码语言：javascript复制
gou_gu(3,20)
代码语言：javascript复制
3
4
5
**********
5
12
13
**********
8
15
17
**********
代码语言：javascript复制
gou_gu(8,20)
代码语言：javascript复制
8
15
17
**********
代码语言：javascript复制
gou_gu(5,20)
代码语言：javascript复制
5
12
13
**********
8
15
17
**********
min return 递归 排序 算法

0 人点赞