Question

如何求两个数的最大公约数

Answer 1

求两个数的最大公约数。
方法1:通过辗转相除法来求两个数的最大公约数
//思路
//排序:首先创建一个临时变量,然后将两个数排序,将较大的数存入a中,将较小的数存入b中
//创建一个while循环,用较大的数去反复取余较小的数,并将取余得到的结果赋值给较小的数
//反复进行上述的while循环直到满足较大的数取余较小的数为0时,跳出循环
//最后输出的较小的数就为这两个数的最大公约数
#include<stdio.h>
#include<windows.h>
int main()
{
int a;
int b;
int t;
printf(“请输入两个数求它们的公约数:”);
scanf_s("%d %d", &a, &b);
if (a < b)//将较大的数的值放入a中
{
t = a;
a = b;
b = t;
}
while (a%b != 0)//反复取余,并把取余所得的值赋给较小的数
{
t = a % b;
a = b;
b = t;
}//理解此处交换变量位置
printf(“这两个数的最大公约数为%d\n”, b);
system(“pause”);
return 0;
}
方法2
//输入两个数求它们的最大公约数
//方法2
//通过辗转相减法来求两个数的最大公约数
//创建两个变量,将较大的数的值放入a中,将较小的数的值放入b中
//创建一个while循环,让a,b两个数进行辗转相减
//将相减得到的值赋给较小的数,直到a与b相减的结果为0,
//输出较小的数就为a,b的最大公约数
#include<stdio.h>
#include<windows.h>
int main()
{
int a;
int b;
int t;
printf(“请输入两个数求它们的最大公约数:”);
scanf_s("%d %d", &a, &b);
if (a < b)//当满足这个if条件时,交换两个数的顺序,将较大的数保存在a中
{
t = a;
a = b;
b = t;
}
while (a - b != 0)
{
t=a-b;
a = b;
b = t;
}
printf(“这两个数的最大公约数为:%d\n”,b);
system(“pause”);
return 0;
}
方法3
//穷举法
//输入两个数求它们的最大公约数
//方法三 穷举法
//创建两个变量,将较大的数的值保存在a中,将较小的数的值保存在b中
//创建一个for循环,创建一个临时变量t,将较小的数的值赋给t;用较大的数较小的数去取余t
//不满足时就t–,直到满足较小的数取余t与较大的数取余t的结果都为0时,跳出循环
//输出的数就为值t就为两个数的最大公约数
#include<stdio.h>
#include<windows.h>
int main()
{
int a;
int b;
int t;
printf(“请输入两个数求它们的最大公约数:”);
scanf_s("%d %d", &a, &b);
if (a < b)//将较大的数的值放在a中
{
t = a;
a = b;
b = t;
}
for (t = b; t > 0; t–)
{
if (a%t == 0 && b%t == 0)
{
break;
}
}
printf(“这两个数的最大公约数为:%d\n”, t);
system(“pause”);
//return 0;
}
还有一种写法,个人不是很理解
#include<stdio.h>
#include<windows.h>
int main()
{
int a;
int b;
int t;
printf(“请输入两个数求它们的最大公约数:”);
scanf_s("%d %d", &a, &b);
if (a < b)//将较大的数的值放在a中
{
t = a;
a = b;
b = t;
}
for (t = b; a%t || b % t; t–);
printf(“这两个数的最大公约数为:%d\n”, t);
system(“pause”);
//return 0;
}
问题:为什么for语句中的循环条件为a%t || b % t而不为a%t&&b%t,不是很理解,不是应该两个都满足才输出吗

Answer 2

如何求两个数的最大公因数