辗转相除法

题目

求最大公约数

代码实现：

#include <stdio.h>
void main()
{
    int a, b, r;
    a = 27, b = 18;
    do
    {
        r = a % b;  
        a = b;      
        b = r;    
    } while (r != 0);  // 余数不为0时继续循环
    printf("最大公约数是：%d\n", a);  // 循环结束后，a就是最大公约数
}

代码分析：

• 辗转相除法（欧几里得算法）

核心逻辑：
两个数的最大公约数，等于「（较大数 ÷ 较小数）的余数」和「较小数」的最大公约数。
一直重复这个过程，直到余数为0，此时的“除数”就是最大公约数。

举个生活例子：
你有27个苹果、18个橘子，想分成一样多的份数（每份数量相同）
27-18=9
如果能分27和18，肯定也能分剩下的9和18

备注

其实我上课看到这一个题的时候第一反应使用while循环进行循环：

#include <stdio.h>

int main() {
	int a, b, temp, i;
	scanf_s("%d,%d", &a, &b);
	if (a < b) {
		temp = a;
		a = b;
		b = temp;
	}
	for (i = b;i >= 1;i--) {
		if (a % i == 0 && b % i == 0) {
			break;
		}
	}
	printf("最大公约数是%d", i);
}

注意

我第一次写这个代码的时候是这么写的：

#include <stdio.h>

int main() {
	int a, b, temp;
	scanf_s("%d,%d", &a, &b);
	if (a < b) {
		temp = a;
		a = b;
		b = temp;
	}
	for (int i = b;i >= 1;i--) {
		if (a % i == 0 && b % i == 0) {
			break;
		}
	}
	printf("最大公约数是%d", i);
}

我在for循环中定义int i，运行的时候提示i是未定义的标识符！！！

• 在 C 语言中，在for循环的初始化部分声明的变量（如int i = b），其作用域仅限于for循环内部。当循环结束后，变量i就会被销毁，外部的printf语句无法访问到它，因此会报错 “未声明的标识符i”。

故修改后：

#include <stdio.h>

int main() {
	int a, b, temp, i;
	scanf_s("%d,%d", &a, &b);
	if (a < b) {
		temp = a;
		a = b;
		b = temp;
	}
	for (i = b;i >= 1;i--) {
		if (a % i == 0 && b % i == 0) {
			break;
		}
	}
	printf("最大公约数是%d", i);
}