Bash 编程: 计算两个正整数的最大公约数/GCD

阅读 桌面完整版

使用 Bash 脚本计算最大公约数（GCD）

什么是 GCD？

• GCD 是 最大公约数（Greatest Common Divisor） 的缩写。
• 它是能同时整除两个整数的最大正整数。
• 例如：
  • 8 和 12 的 GCD 是 4
  • 14 和 49 的 GCD 是 7
• GCD 常用于化简分数、密码算法以及数论中。

计算 GCD 的常见算法

1. 欧几里得算法

• 最常见且高效的算法。
• 基于这样一个原理：gcd(a, b) = gcd(b, a % b)
• 重复上述步骤直到 b 为 0，此时 a 即为最大公约数。

2. 减法法

• 不断用较大的数减去较小的数，直到两个数相等。
• 结果就是它们的 GCD。
• 相比欧几里得算法，这种方法在处理大数时效率较低。

3. 二进制 GCD 算法（Stein 算法）

• 使用位运算代替除法运算。
• 在某些硬件中更高效，因为避免了除法和取模操作。
• 基于以下规则：
  • 若两个数都为偶数：gcd(a, b) = 2 * gcd(a/2, b/2)
  • 若其中一个是偶数，则将其除以 2
  • 若两个数都为奇数，且 a > b，则 gcd(a, b) = gcd((a - b)/2, b)

功能概述

• 该脚本计算两个数字的最大公约数（GCD）
• 确保输入参数是正整数
• 当输入缺失或无效时，提供用法说明

脚本功能解释

• gcd() 函数： 使用循环和取模操作实现欧几里得算法。
• 参数个数检查： 确保用户传入了两个参数，否则提示用法并退出。
• 正则校验： 使用 Bash 正则判断两个输入是否为纯数字。
• 范围校验： 确保两个数字都大于零。
• 函数调用： 调用 gcd 函数并输出结果。

计算两正整数最大公约数GCD的BASH函数

以下是计算GCD的BASH代码。

#!/bin/bash

## 计算两个数的最大公约数

gcd() {
    local a=$1
    local b=$2

    while [ $b -ne 0 ]; do
        local temp=$b
        b=$((a % b))
        a=$temp
    done

    echo $a
}

# 检查是否传入了两个参数
if [ $# -ne 2 ]; then
    echo "用法: $0 <number1> <number2>"
    exit 1
fi

## 检查两个参数是否为正整数
if ! [[ $1 =~ ^[0-9]+$ ]] || ! [[ $2 =~ ^[0-9]+$ ]]; then
    echo "两个参数必须为正整数。"
    exit 1
fi
if [ $1 -le 0 ] || [ $2 -le 0 ]; then
    echo "两个参数都必须大于零。"
    exit 1
fi

# 调用 gcd 函数并打印结果
result=$(gcd "$1" "$2")
echo $result

输入校验流程

1. 检查是否传入了两个参数
2. 使用正则表达式确保输入为整数：=~ ^[0-9]+$
3. 确保两个数都大于 0

使用示例

两个互质整数co-prime，它们的最大公约数为1。

命令	输出
./gcd.sh 24 36	12
./gcd.sh 7 13	1

小提示：

• 使用 chmod +x gcd.sh 让脚本可执行
• 然后运行：./gcd.sh 12 30

BASH小技巧

• Bash 编程: 计算两个正整数的最大公约数/GCD
• BASH: 如何使用 cURL 命令获取 HTTP 响应代码?
• 通过BASH脚本显示树莓PI的温度和频率
• 如何通过BASH命令把频繁访问服务器的IP找出来?
• BASH编程: 计算一个文本文件中每个单词的频率
• LINUX BASH下的 大括号数组
• BASH 脚本 防止 iptablex 攻击
• BASH 脚本匹配 IP 地址的 简单例子 (正则表达式)
• 如何在 Linux 下 列出最耗资源的进程 (BASH 脚本)
• BASH: 通过dd命令测试硬盘读写速度/性能
• 判断服务器的硬盘类型: 是否是固态硬盘/NVMe
• LINUX 命令 cowsay, cowthink 牛说/牛想
• BASH: 怎样通过curl命令查看服务器响应时间??
• BASH: LINUX 下竖中指

英文：Compute GCD in Bash with Input Validation

微信公众号: 小赖子的英国生活和资讯 JustYYUK

阅读 桌面完整版