Question

什么是约数？怎么求约数

Answer 1

整数a除以整数b(b≠0) 除得的商正好是整数而没有余数，我们就说a能被b整除，或b能整除a。a叫b的倍数，b叫a的约数（或因数）。在大学之前，所指的一般都是正约数。约数和倍数相互依存，不能单独说某个数是约数或倍数。一个数的约数是有限的。
　1、 枚举法 将两个数的因数分别一一列出，从中找出其公因数，再从公因数中找出最大的一个，即为这两个数的最大公因数。 　　例：求30与24的最大公因数。 　　30的因数有：1,2,3,5,6,10,15,30 　　24的因数有：1,2,3,4,6,8,12,24 　　易得其公因数中最大的一个是6，所以30和24的最大公因数是6。 　　2、 短除法 短除符号就像一个倒过来的除号，短除法就是先写出要求最大公因数的两个数A、B，再画一个短除号，接着在原本写除数的位置写两个数公有的质因数Z（通常从最小的质数开始），然后在短除号的下方写出这两个数被Z整除的商a，b，对a，b重复以上步骤，以此类推，直到最后的商互质为止，再把所 求12和18的最大公约数
有的除数相乘，其积即为A，B的最大公因数。 短除法
（短除法同样适用于求最小公倍数，只需将其所有除数与最后所得的商相乘即可） 　　例：求12和18的最大公约数。 　　解：用短除法，由左图，易得12和18的最大公约数为2×3=6.。 　　3、分解质因数将需要求最大公因数的两个数A，B分别分解质因数，再从中找出A、B公有的质因数，把这些公有的质因数相乘，即得A、B的最大公约数。 　　例：求48和36的最大公因数。 　　把48和36分别分解质因数： 　　48=2×2×2×2×3 　　36=2×2×3×3 　　其中48和36公有的质因数有2、2、3，所以48和36的最大公因数是 2×2×3=12。 　　4、辗转相除法（欧几里得算法）对要求最大公因数的两个数a、b，设b<a，先用b除a，得a=bq……r1(0≤r1<b)。若r1=0，则(a，b)=b；若r1≠0，则再用r1除b，得b=r1q……r2 (0≤r2<r1).，若r2=0，则(a，b)=r1，若r2≠0，则继续用r2除r1……如此循环，直到能整除为止。其最后一个非零余数即为(a，b)。 　　这一算法的证明如下： 　　设两数为a、b(b<a)，用gcd(a,b)表示a，b的最大公约数，r=a mod b 为a除以b以后的余数，辗转相除法即是要证明gcd(a,b)=gcd(b,r)。 　　令c=gcd(a,b)，则设a=mc，b=nc，根据前提有r =a-kb=mc-knc=(m-kn)c 　　由上，可知c也是r的因数，故可以断定m-kn与n互素【否则，可设m-kn=xd，n=yd，(d>1)，则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)dc，b=nc=ycd，故a与b最大公因数成为cd，而非c】 　　所以 gcd(b,r)=c，继而gcd(a,b)=gcd(b,r)。 　　例：求8251和6105的最大公因数。 　　考虑用较大数减较小数，求得商和余数： 　　8251=6105×1+2146 　　6105=2146×2+1813 　　2146=1813×1+333 　　1813=333×5+148 　　333=148×2+37 　　148=37×4 　　最后除数37是148和37的最大公因数，也就是8251与6105的最大公因数。

Answer 2

求一个数的
约数
(
因数
)是把它拆成两个数相乘，每两个都是这个数的约数(因数)
如42=1*42=2*21=3*14=6*7，其中1，42，2，21，3，14，6，7都是42的约数(因数)