互质数的C语言程序,并附有解释
时间: 2025-07-01 10:35:55 浏览: 9
### C语言实现输出1到100之间的互质数
以下是基于最大公约数(GCD)的概念来判断两个数是否互质的方法。如果两数的最大公约数为1,则这两个数互质。
#### 方法描述
为了找到1到100之间所有的互质数对,可以采用双重循环遍历每一对可能的组合,并通过计算其最大公约数来验证是否满足条件。这里提供了一个完整的C语言程序示例:
```c
#include <stdio.h>
// 定义求解最大公约数的函数
int gcd(int i, int j) {
return j ? gcd(j, i % j) : i;
}
int main() {
int count = 0;
// 遍历1到100的所有整数对
for (int i = 1; i <= 100; i++) {
for (int j = i + 1; j <= 100; j++) {
if (gcd(i, j) == 1) { // 如果最大公约数为1,则说明两者互质
printf("(%d, %d)\n", i, j);
count++;
}
}
}
printf("\nTotal number of coprime pairs between 1 and 100: %d\n", count);
return 0;
}
```
#### 关键点解析
- **最大公约数算法**:使用欧几里得算法递归地求解两个数的最大公约数[^1]。
- **双重循环结构**:外层循环控制第一个数`i`,内层循环控制第二个数`j`,其中`j`总是大于`i`以避免重复计数。
- **互质判定**:当且仅当`gcd(i, j)`的结果等于1时,认为`(i, j)`是一对互质数。
运行此代码后,将会打印出所有位于区间[1, 100]内的互质数对及其总数。
#### 示例输出
假设执行以上代码片段,部分输出如下所示:
```
(1, 2)
(1, 3)
(1, 4)
...
(98, 99)
(98, 100)
Total number of coprime pairs between 1 and 100: XXXX
```
请注意,实际总数量取决于具体逻辑运算结果。
---
### 解释
- **gcd 函数**:这是一个递归函数,用来计算两个正整数 `i` 和 `j` 的最大公约数。它利用了欧几里得算法的核心原理——两个整数的最大公约数等于较小的那个数和两数相除余数的最大公约数[^1]。
- **for 循环嵌套**:外部循环变量 `i` 表示当前考虑的第一个数;内部循环变量 `j` 则表示与 `i` 进行比较的另一个数。由于 `(i, j)` 和 `(j, i)` 是相同的互质关系,因此只需让 `j > i` 即可减少冗余计算。
- **printf 打印**:对于每一组符合条件的互质数对 `(i, j)`,都会立即输出至标准输出设备。
- **count 计数器**:记录并统计最终得到的有效互质数对数目,在最后统一展示出来。
---
阅读全文
相关推荐


















