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

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

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

您好，在求最大公约数时,一般先用最小的公约数去除,直到得数为互质数时为止,再将所有的公约数相乘,积就是几个数的最大公约数。
举个例子：
以12和16为例，两者先都除以2，得6,8。
6和8还可以继续除以2，得到3,4。
3,4互为质数，不可再除。
所以12,和16的最大公约数就等于2乘2，得4。
最大公因数，也称最大 公约数、最大公 因子，指两个或多个 整数共有 约数中最大的一个。 a， b的最大公约数记为（a，b），同样的，a，b，c的最大 公约数记为（a，b，c），多个 整数的最大公约数也有同样的记号。求最大公约数有多种 方法，常见的有 质因数分解法、 短除法、 辗转相除法、 更相减损法。与最大公约数相对应的概念是 最小公倍数，a，b的 最小公倍数记为[a，b]。

求两个数的最大公约数。
方法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,不是很理解,不是应该两个都满足才输出吗

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

---

霍州市13744303645： 如何求两个数的最大公约数 - ？
赤薛回春：[答案] 大公约数 将它们分解质因数,找出其中相同的质因数,再将它们相乘,就得到了最大公约数,如果两数的质因数中,没有一个是相同的,那么它们的最大公约数就是1.比如(56,42) 56=7*2*2*2 42=7*2*3 其中7,2是相同的,那么它们的最大公约数...

霍州市13744303645： 求两个自然数的最大公约数有哪些方法? - ？
赤薛回春： 方法如下:1、质因数分解法 把每个数分别分解质因数,再把各数中的全部公有质因数提取出来连乘,所得的积就是这几个数的最大公约数. 例如:求24和60的最大公约数,先分解质因数,得24=2*2*2*3,60=2*2*3*5,24与60的全部公有的质...

霍州市13744303645： 求最大公约数?怎么求? 具体的方法和过程 - ？
赤薛回春： 若A、B都是N的倍数,则A-B仍然是N的倍数. 也就是把两个数相减,不会使约数消失. 那么可以用互相减的办法,把数字化小,直到一个数是另一个数的倍数. 如:216与504 504-216=288 变成:288与216(因为约数不会减少,相当于求288与216的公约数) 288-216=72 变成:216与72 216=72*3 最大公约数是72

霍州市13744303645： 求两个数的最大公约数有哪几种方法?如求120和254??过程也要 - ？
赤薛回春： 用辗转相除法 设两数为a、b(b

霍州市13744303645： 如何求两数的最大公约数? - ？
赤薛回春： 最大公约数 将它们分解质因数,找出其中相同的质因数,再将它们相乘,就得到了最大公约数,如果两数的质因数中,没有一个是相同的,那么它们的最大公约数就是1. 比如(56,42) 56=7*2*2*2 42=7*2*3 其中7,2是相同的,那么它们的最大公约数就是2*7=14

霍州市13744303645： 两个整数的最大公约数如何计算? - ？
赤薛回春：[答案] 用分解质因数的方法,求两个整数的最大公约数,一般用这两个数公有的质因数去除,一直除到所得的商是互质数为止,把所有的除数连乘起来

霍州市13744303645： 求两个数的最大公约数和最小公倍数的算法 - ？
赤薛回春：[答案] 分别把两个数做质因数分解, 把相同质因数跳出来,取两者较小的次幂乘起来,就是最大公约数 两个数的积除以最大公约数,就是最小公倍数 比如说12和40 12=2^2*3 40=2^3*5 最大公约数=2^2=4 最小公倍数=12*40/4=120

霍州市13744303645： 最大公约数的求法 - ？
赤薛回春： 求两个数的最大公约数的方法 (1)用短除法求两个数的最大公约数,一般先用这两个数公有的质因数连续去除,一直除到所得的商是互质数为止,然后把所有的除数连乘起来,在除的过程中,有时也可以用两个数的公约数去除. (2)求两个数的最大公约数的两种特殊情况:①如果这两个数存在着倍数关系(即较大数是较小数的倍数),那么,较小数就是这两个数的最大公约数;②如果两个数是互质数,那么它们的最大公约数就是1.

霍州市13744303645： 求两个数的最大公约数有几种方法 - ？
赤薛回春： 方法一:短除法 方法二:分别写出两个数的所有约数,作对比,有相同的数,全部乘起来. 方法三:把这两数写成分数形式,然后化简成最简分数,和原数相比,约分了多少,最大公约数即是多少.

霍州市13744303645： 怎样用数学方法求两个数的最大公约数 - ？
赤薛回春：[答案] a b 除数 84 60 2 42 30 2 21 15 3 7 5 最大公约数:2*2*3=12