C语言如何判断两个数为互质数：使用辗转相除法、求最大公约数、判断是否为1

创作时间:

作者:

@小白创作中心

C语言如何判断两个数为互质数：使用辗转相除法、求最大公约数、判断是否为1

引用

来源

https://docs.pingcode.com/baike/1102504

互质数是指两个数的最大公约数为1的数对。在C语言中，判断两个数是否为互质数的关键在于求解两个数的最大公约数（GCD）。如果两个数的最大公约数为1，则这两个数是互质数。其中，辗转相除法（欧几里得算法）是一种高效求解最大公约数的方法。本文将详细介绍这一过程，并提供相关的C语言代码示例。

辗转相除法的原理

辗转相除法，也称欧几里得算法，是一种用于求解两个整数最大公约数的算法。其基本原理是通过不断取余数，直至余数为零，最后得到的非零余数即为最大公约数。

算法步骤

给定两个整数a和b（假设a > b），计算a除以b的余数r。
若r为0，则b即为a和b的最大公约数，算法结束。
若r不为0，则将a替换为b，b替换为r，重复步骤1和2，直到余数为0。

算法示例

假设要计算48和18的最大公约数，具体步骤如下：

48 ÷ 18 = 2 余数 12
18 ÷ 12 = 1 余数 6
12 ÷ 6 = 2 余数 0

当余数为0时，最后一个非零余数6即为48和18的最大公约数。

C语言实现辗转相除法

下面是一个用C语言实现辗转相除法的函数：

#include <stdio.h>

// 函数声明
int gcd(int a, int b);

// 主函数
int main() {
    int num1, num2;
    // 输入两个整数
    printf("请输入两个整数: ");
    scanf("%d %d", &num1, &num2);
    // 调用gcd函数判断是否互质
    if (gcd(num1, num2) == 1) {
        printf("%d 和 %d 是互质数\n", num1, num2);
    } else {
        printf("%d 和 %d 不是互质数\n", num1, num2);
    }
    return 0;
}

// 求最大公约数的函数
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

代码详解

输入和输出

在main函数中，首先提示用户输入两个整数，然后使用scanf函数读取用户输入的两个数，并将其存储在num1和num2变量中。

调用`gcd`函数

gcd函数用于计算两个数的最大公约数。在main函数中，调用gcd函数并传递num1和num2作为参数。如果返回值为1，则这两个数是互质数，程序输出相应的提示信息；否则，输出两个数不是互质数。

实现`gcd`函数

gcd函数实现了辗转相除法的算法。函数参数a和b分别表示两个整数。在while循环中，不断计算a除以b的余数，并将a替换为b，b替换为余数，直到余数为0。最后返回a作为最大公约数。

优化与扩展

优化输入校验

在上述代码中，我们没有对用户输入进行校验。为了提高程序的健壮性，可以添加输入校验代码，确保用户输入的是有效的整数。

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

// 函数声明
int gcd(int a, int b);

// 输入校验函数
int getIntFromUser() {
    char buffer[20];
    while (1) {
        fgets(buffer, sizeof(buffer), stdin);
        char *endptr;
        int val = strtol(buffer, &endptr, 10);
        if (endptr == buffer || *endptr != '\n') {
            printf("无效输入，请输入一个整数: ");
        } else {
            return val;
        }
    }
}

// 主函数
int main() {
    int num1, num2;
    // 输入两个整数
    printf("请输入第一个整数: ");
    num1 = getIntFromUser();
    printf("请输入第二个整数: ");
    num2 = getIntFromUser();
    // 调用gcd函数判断是否互质
    if (gcd(num1, num2) == 1) {
        printf("%d 和 %d 是互质数\n", num1, num2);
    } else {
        printf("%d 和 %d 不是互质数\n", num1, num2);
    }
    return 0;
}

// 求最大公约数的函数
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

处理负数输入

在实际应用中，用户可能会输入负数。为保证程序的正确性，可以在计算最大公约数前，将输入的负数转换为正数。

#include <stdio.h>
#include <stdlib.h>

// 函数声明
int gcd(int a, int b);

// 主函数
int main() {
    int num1, num2;
    // 输入两个整数
    printf("请输入第一个整数: ");
    num1 = getIntFromUser();
    printf("请输入第二个整数: ");
    num2 = getIntFromUser();
    // 转换为正数
    num1 = abs(num1);
    num2 = abs(num2);
    // 调用gcd函数判断是否互质
    if (gcd(num1, num2) == 1) {
        printf("%d 和 %d 是互质数\n", num1, num2);
    } else {
        printf("%d 和 %d 不是互质数\n", num1, num2);
    }
    return 0;
}

// 求最大公约数的函数
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}