基本概念
-
因数 ：若A=m×n，则称m，n是A的因数；A是m，n的倍数 一个数的最大因数和最小倍数都是它本身
一个数的最小因数是1。 - 质数（素数）：在大于1的整数中，只有1和它本身两个因数的数，叫做质数。** 0、1既不是质数也不是合数；2 是唯一的偶数质数**。
- 约数：若A÷B=x„0（A能够整除B，没有余数）； 则称B是A的约数；A是B的倍数
- 质约数：如果一个整数的约数恰好是一个质数，则称此约数为这个整数的质约数
- 分解质因数（分解质约数）：把一个整数分解成多个质因数（约数）连乘 标准分解质因数的写法：把小的写在前面，多个相同的质数要用乘方表示。
宣传语
历经两个半月的准备，三次大改版，十七次小改版。le1024终于要和大家见面了。
le1024每天推荐1~3段，有趣、有爱、有故事的视频。
为您工作、学习、生活之余增加一点快乐的感觉。
- 互质, 也称之为互素。若N个整数的最大公因子是1，则称这N个整数互质。
-
合数：在大于2的整数中，除了1和它本身两个因数，还有其它因数的数，叫做合数
整数a除以整数b(b≠0) 除得的商正好是整数而没有余数，我们就说a能被b整除，或b能整除a。a叫b的倍数，b叫a的约数（或 因数）。一个数的约数是有限的。
什么是最大公约数
最大公约数，也称最大公因数、最大公因子，指两个或多个整数共有约数中最大的一个。
如，12 和 30 的约数，以及公有的约数。
那么可知，12和30的最大公约数为6
辗转相除法
两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的相除余数的最大公约数 。
例如，252和105的最大公约数是21（252 = 21 × 12；105 = 21 × 5）；因为252 / 105 = 2余42，所以105和42的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至余数变为零。这时的除数就是所求的两个数的最大公约数。
辗转相除法的演示动画：两条线段分别表示252和105，其中每一段表示21。动画演示了循环从大数中减去小数，直到其中一段的长度为0，此时剩下的一条线段的长度就是252和105的最大公约数。
条形表示法：
最初的绿色矩形的长和宽分别是a = 1071、b = 462，从中不断铺上462×462的正方形直到剩下部分面积是462×147；然后再铺上147×147的正方形直至剩下21×147的面积；最后，铺上21×21的正方形时，绿色部分就没有了。即21是1071和462的最大公约数.
瓷砖表示法：
数学表示：
f(x,y) = f(y, x % y)
ruby 代码：
def gcd(x , y)
return (y == 0 )? x : gcd(y , x % y)
end
用辗转相除法求几个数的最大公约数，可以先求出其中任意两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数，依次求下去，直到最后一个数为止。最后所得的那个最大公约数，就是所有这些数的最大公约数。
时间复杂度：
O(log n），其中 n 为输入数值的位数。
相减法
以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
例如：91和49
| 较大值 | 较小值 |
|---|---|
| 91 | 49 |
| 49 | 42 |
| 42 | 7 |
| 35 | 7 |
| 28 | 7 |
| 21 | 7 |
| 14 | 7 |
| 7 | 7 |
数学表示：
f(x,y) = f(x-y, y)
ruby 代码：
def gcd2(x , y)
if(x < y)
return gcd2(y , x)
elsif(y == 0)
return x
else
return gcd2(x - y , y)
end
end
时间复杂度： < O(log n）
此解法用减法而不是除法，降低了计算的复杂度，但是迭代的次数比除法要多，当遇到f(10000000,1)的情况时这不是一个好方法。
相除法和想减法的区别
（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。
（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到。
融合以上两种方式
首先，从公约数的特点入手
- x和y来说，如果
x = k * x1, 那么y = k * y1,那么就有f(x, y) = k * f(x1, y1) - 如果
x = p * x1, 假设p是素数，并且y % p!=0(即y不能被p整除, 若等于0，那么y就是最大公约数)，那么f(x, y) = f(p * x1, y) = f(x1, y) - 2是一个素数，同时对于二进制表示的大整数而言，可以很容易地除以2和乘以2的运算转换成移位运算，从而避免大整数除法，由此可以利用2这个数字来进行分析
数学的表示方法
取 p = 2
若x, y 均为偶数 f(x,y)= 2 * f(x/2,y/2) = 2 * f(x >> 1, y>>1)
若x为偶数，y为奇数 f(x,y) = f(x/2, y) = f(x >> 1, y)
若x为奇数，y为偶数 f(x,y) = f(x, y/2) = f(x, y >> 1)
若x, y均为奇数 f(x, y) = f(y, x-y)
那么在f(x,y) = f(y, x- y)之后，(x - y)是一个偶数，下一步就是除以2的操作
ruby 代码
def gcd3(x ,y)
if(x < y)
return gcd3(y, x)
end
if(y == 0)
return x
else
if(is_even?(x))
if (is_even?(y))
return (gcd3(x >> 1, y >> 1) << 1)
else
return gcd3(x >> 1, y)
end
else
if(is_even?(y))
return gcd3(x, y >> 1)
else
return gcd3(y, x-y)
end
end
end
end
def is_even?(a)
if(a%2 == 0)
return true
else
return false
end
end
时间复杂度
O(log2(max(x,y)))
附
辗转相除法证明：
设两数为a、b(b<a），用gcd(a,b）表示a，b的最大公约数，r=a mod b 为a除以b以后的余数，k为a除以b的商，即a÷b=k.......r。辗转相除法即是要证明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）。
