方法一:辗转相除法
又名欧几里德算法（Euclidean algorithm），是求最大公约数的一种方法。它的具体做法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。
#define _CRT_SECURE_NO_WARNINGS
#include
int main() {
int a, b;
int min,max,temp;
printf("请输入两个数字:\n");
scanf("%d %d", &a, &b);
min = a > b ? b : a;
max = a > b ? a : b;
while (max%min != 0) {
temp = max%min;
max = min;
min = temp;
}
if (min == 1) {
printf("这两个数互质.");
}
else {
printf("这两个数字的最大公约数为:%d\n", min);
}
return 0;
}
方法二:循环遍历
#define _CRT_SECURE_NO_WARNINGS
#include
int main() {
int a, b;
int min,max;
printf("请输入两个正整数:\n");
scanf("%d %d", &a, &b);
min = a < b ? a : b;
for (int i = 2;i <= min;i++) {
if (a%i == 0 && b%i == 0) {
max = i;
}
}
printf("最大公约数是:%d", max);
return 0;
}
上述代码问题: 如果两个数互质如(4和5) 则会出现如下错误
意思为变量max没有被初始化,因此在前面定义max时给max赋一个初值0.
此时需要加一个if语句说明这两个数互质 更改后的代码为:
#define _CRT_SECURE_NO_WARNINGS
#include
int main() {
int a, b;
int min;
int max = 0;
printf("请输入两个正整数:\n");
scanf("%d %d", &a, &b);
min = a < b ? a : b;
for (int i = 2;i <= min;i++) {
if (a%i == 0 && b%i == 0) {
max = i;
}
}
if (max == 0) {
printf("这两个数互质!\n");
}
else {
printf("最大公约数是:%d\n", max);
}
return 0;
}
方法三:辗转相减法
辗转相减法是一种简便的求出两数最大公约数的方法。（更相减损术）
辗转相减法（求最大公约数），即尼考曼彻斯法，其特色是做一系列减法，从而求得最大公约数。例如 ：两个自然数35和14，用大数减去小数，(35,14)->(21,14)->(7,14)，此时，7小于14，要做一次交换，把14作为被减数，即(14,7)->(7,7)，再做一次相减，结果为0，这样也就求出了最大公约数7
代码如下:
#define _CRT_SECURE_NO_WARNINGS
#include
int main() {
int a, b;
int min, max;
int temp;
printf("请输入两个正整数:\n");
scanf("%d %d", &a, &b);
min = a > b ? b : a;
max = a > b ? a : b;
while (max - min != 0) {
temp = max - min;
max = temp > min ? temp : min;
min = temp > min ? min : temp;
}
printf("最大公约数是:%d\n", max);
return 0;
}
以上只是本人拙见 多有纰漏望指出 !