如何用 C 语言求最大公约数（GCD）

简介

在本实验中，你将学习如何在C程序中使用欧几里得算法来找到两个整数的最大公约数（GCD）。你将首先从用户输入中读取两个整数，然后应用欧几里得算法来计算它们的GCD，最后打印结果。本实验涵盖了数论和离散数学中的基本概念，使用C编程语言提供了这些原理的实际应用。

Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL c(("C")) -.-> c/BasicsGroup(["Basics"]) c(("C")) -.-> c/FunctionsGroup(["Functions"]) c(("C")) -.-> c/UserInteractionGroup(["User Interaction"]) c/BasicsGroup -.-> c/variables("Variables") c/BasicsGroup -.-> c/operators("Operators") c/FunctionsGroup -.-> c/math_functions("Math Functions") c/UserInteractionGroup -.-> c/user_input("User Input") c/UserInteractionGroup -.-> c/output("Output") subgraph Lab Skills c/variables -.-> lab-435183{{"用 C 语言求最大公约数（GCD）"}} c/operators -.-> lab-435183{{"用 C 语言求最大公约数（GCD）"}} c/math_functions -.-> lab-435183{{"用 C 语言求最大公约数（GCD）"}} c/user_input -.-> lab-435183{{"用 C 语言求最大公约数（GCD）"}} c/output -.-> lab-435183{{"用 C 语言求最大公约数（GCD）"}} end

读取两个整数

在这一步中，你将学习如何在C程序中从用户输入读取两个整数，以找到它们的最大公约数（GCD）。

首先，让我们为我们的GCD程序创建一个新的C文件：

cd ~/project
nano gcd.c

现在，添加以下代码来读取两个整数：

#include <stdio.h>

int main() {
    int num1, num2;

    printf("输入第一个整数：");
    scanf("%d", &num1);

    printf("输入第二个整数：");
    scanf("%d", &num2);

    printf("第一个数字：%d\n", num1);
    printf("第二个数字：%d\n", num2);

    return 0;
}

让我们来分析一下这段代码：

scanf() 用于从用户读取整数输入
%d 是整数的格式说明符
&num1 和 &num2 将变量的内存地址传递过去以存储输入

编译并运行该程序：

gcc gcd.c -o gcd
./gcd

示例输出：

输入第一个整数：48
输入第二个整数：18
第一个数字：48
第二个数字：18

应用欧几里得算法

在这一步中，你将实现欧几里得算法来找出两个整数的最大公约数（GCD）。

打开之前的 gcd.c 文件并进行修改，以包含GCD计算：

cd ~/project
nano gcd.c

用欧几里得算法的实现更新代码：

#include <stdio.h>

// 使用欧几里得算法计算GCD的函数
int calculateGCD(int a, int b) {
    // 确保为正数
    a = (a > 0)? a : -a;
    b = (b > 0)? b : -b;

    // 欧几里得算法
    while (b!= 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }

    return a;
}

int main() {
    int num1, num2, gcd;

    printf("输入第一个整数：");
    scanf("%d", &num1);

    printf("输入第二个整数：");
    scanf("%d", &num2);

    // 计算GCD
    gcd = calculateGCD(num1, num2);

    printf("第一个数字：%d\n", num1);
    printf("第二个数字：%d\n", num2);
    printf("最大公约数：%d\n", gcd);

    return 0;
}

让我们来分析一下欧几里得算法的实现：

该算法反复用较大的数除以较小的数
它使用取模运算符 % 来得到余数
这个过程一直持续到余数变为0
最后一个非零余数就是GCD

编译并运行程序：

gcc gcd.c -o gcd
./gcd

示例输出：

输入第一个整数：48
输入第二个整数：18
第一个数字：48
第二个数字：18
最大公约数：6

打印最大公约数

在这一步中，你将对最大公约数（GCD）结果进行格式化并打印，同时添加更多背景信息，使输出更具信息量。

打开之前的 gcd.c 文件，并对输出添加一些格式设置：

cd ~/project
nano gcd.c

更新代码以增强GCD输出：

#include <stdio.h>

// 使用欧几里得算法计算GCD的函数
int calculateGCD(int a, int b) {
    // 确保为正数
    a = (a > 0)? a : -a;
    b = (b > 0)? b : -b;

    // 欧几里得算法
    while (b!= 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }

    return a;
}

int main() {
    int num1, num2, gcd;

    printf("最大公约数（GCD）计算器\n");
    printf("----------------------------------------\n");

    printf("输入第一个整数：");
    scanf("%d", &num1);

    printf("输入第二个整数：");
    scanf("%d", &num2);

    // 计算GCD
    gcd = calculateGCD(num1, num2);

    // 格式化输出
    printf("\n结果：\n");
    printf("第一个数字：  %d\n", num1);
    printf("第二个数字： %d\n", num2);
    printf("GCD：         %d\n", gcd);

    // 额外解释
    printf("\n解释：\n");
    printf("最大公约数（GCD）是能同时整除这两个数且不留下余数的最大正整数。\n");

    return 0;
}

编译并运行程序：

gcc gcd.c -o gcd
./gcd

示例输出：

最大公约数（GCD）计算器
----------------------------------------
输入第一个整数：48
输入第二个整数：18

结果：
第一个数字：  48
第二个数字： 18
GCD：         6

解释：
最大公约数（GCD）是能同时整除这两个数且不留下余数的最大正整数。

主要改进：

添加了标题和分隔符
以对齐的列格式化输出
包含了GCD概念的解释
保留了核心的GCD计算逻辑

总结

在本实验中，你首先学习了如何使用 scanf() 函数从用户输入中读取两个整数。然后，你实现了欧几里得算法来计算这两个数的最大公约数（GCD）。欧几里得算法是一种通过反复应用取模运算直到余数变为零来高效找到GCD的方法，此时GCD就是最后一个非零余数。最后，你打印了计算出的GCD。