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

小赖子的英国生活和资讯

作者 JustYY.com 小赖子的英国生活和资讯

2025年6月19日 05:36

使用 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

输入校验流程

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

使用示例

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

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

小提示：

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

BASH小技巧

英文：Compute GCD in Bash with Input Validation

本文一共 599 个汉字, 你数一下对不对.

Bash 编程: 计算两个正整数的最大公约数/GCD. (AMP 移动加速版本)

赞赏我的几个理由.

¥ 打赏支持

扫描二维码，分享本文到微信朋友圈

75a5a60b9cac61e5c8c71a96e17f2d9c Bash 编程: 计算两个正整数的最大公约数/GCD BASH BASH 学习笔记数学程序设计算法计算机

The post Bash 编程: 计算两个正整数的最大公约数/GCD first appeared on 小赖子的英国生活和资讯.

步步高学生电脑上 Basic 编程语言 peek 用法示例步步高学生电脑是8位FC机的经典之作.它上面的BASIC有三个版本 1.0, 2.0 和 2.1 2.1 版本有个在线帮助,实际上是 help.cmd 1.0 是用 Esc 键退回到 DOS 的,...
按揭贷款(房贷,车贷) 每月还贷计算器去年给银行借了17万英镑买了20万7500英镑的房子, 25年还清. 前2年是定率 Fix Rate 的合同 (年利率2.49%). 每个月大概是还 700多英镑. 有很多种还贷的计算方式, 定率/每月固定是比较常用的. 简单来说就是每个月交的钱是...
穷举算法的应用 – 去除EXCEL文件中的保护 EXCEL 是可以用密码来保护的. 比如这个EXCEL 就用了密码保护. 打开EXCEL文件你会注意到无法编辑无法查看宏(VBA)的代码. 去除保护很简单第一步先编辑宏 VBA 把下面的VBA代码拷贝到VBA编辑器里并按下F5运行 1...
智能手机 HTC One M9 使用测评虽然我对手机要求不高, 远远没有像追求VPS服务器一样, 但是怎么算来两年内换了四个手机, 先是三星 S4 用了一年多, 然后 Nokia Lumia 635 Windows Phone, 后来又是 BLU, 半年多前换了...
一张图告诉你北京的雾霾有多严重一北京的朋友朋友圈发的: 左上为全新口罩;右上为全新口罩本周一到周五每天室外戴20分钟左右;左下为全新口罩今早室外+公交车戴一个半小时;右下为全新口罩今早开车戴一小时左右. 还有这图空气污染 – 红色的是严重的.中国,尤其是华北地区,是全球最红的地区,没有”之一”. 本文一共 113 个汉字, 你数一下对不对. 一张图告诉你北京的雾霾有多严重. (AMP 移动加速版本) 赞赏我的几个理由. ¥...
世界再无OneKey币圈美元虚拟卡了我前两年就了解到OneKey这个币圈虚拟货币出金卡，不过去年年底才注册使用的。当时还花了99美元一步升级到顶级黑卡。然后这一年陆陆续续用了这卡，但用得不多，主要就用于支持一些VPS主机费还有CloudFlare，ChatGPT Pro等。这个卡是美国地址，卡号有两个段，Visa 和 Mastercard，不过由于地址是美国的，刷卡可能会有问题。比如我ChatGPT Pro注册帐号是英国的，然后用这卡支付了几个月，突然有一天帐号就被封，被告知：您的付款记录很可疑。印象中，用这虚拟货币Crypto Card美元出金卡有手续费，但是并没有啥Cash Back返现卡，如果是非美元购物则会有另一笔手续费，所以我很少用这卡出金变现。前两个月，OneKey宣布关闭：关于 OneKey Card 服务停用通知尊敬的用户，为提高服务质量和优化产品供应，我们将按照以下时间表停用...
英国房子的EPC节能报告(Energe/Efficiency Performance Certificate) EPC (Energe/Efficiency Performance Certificate) 是英国房子的节能报告, 法律上规定, 每个房子都必须要有一个EPC报告, 报告的有效期为十年. 房东在把房子出租或者想卖房的时候, 这个EPC就必须有效, 在一些情况下比如出租房子的时候, 这个EPC报告还必须符合一些最低标准, 比如房子必须满足 F档(类似及格线)...
WordPress 最简单的过滤垃圾评论的方法 WordPress 很多垃圾评论都是由程序直接调用访问 wp_comments.php 造成的. 所以我们可以在 functions.php 文件里加入以下代码新增一个过滤简单的检查是否是直接调用. 1 2 3 4 5 6...

普通视图

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

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

什么是 GCD？

计算 GCD 的常见算法

1. 欧几里得算法

2. 减法法

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

功能概述

脚本功能解释

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

输入校验流程

使用示例

小提示：

BASH小技巧

相关文章：