宽屏网站和普通网站,icp备案信息查询,做淘宝客网站推广被骗,沈阳市做网站电话最大公因数#xff08;英语#xff1a;highest common factor#xff0c;hcf#xff09;也称最大公约数#xff08;英语#xff1a;greatest common divisor#xff0c;gcd#xff09;是数学词汇#xff0c;指能够整除多个非零整数的最大正整数。例如8和12的最大公因数…最大公因数英语highest common factorhcf也称最大公约数英语greatest common divisorgcd是数学词汇指能够整除多个非零整数的最大正整数。例如8和12的最大公因数为4。表示gcd(8,12) 4
最小公倍数英语least common multiplelcm是数论中的一个概念。若有一个数X可以被另外两个数A,B整除且X同时大于或等于A和B则X为A和B的公倍数。A和B的公倍数有无限个而所有正的公倍数中最小的公倍数就叫做最小公倍数。例如8和12的最小公倍数为24。表示lcm(8,12) 24
两个整数的最小公倍数与最大公因数之间有如下的关系 根据上面的示例|8*12|/424
也就是说我们掌握了最大公约数的求法也就能求最小公倍数
那么我们就以最大公约数为例
枚举(穷举)
根据已有的数学知识我们知道mn的话m,n的最大公约数永远不可能是m因为n/m不能整除最大只可能是n。所以我们只需要从n开始依次向较小数找到“能同时被n,m整除的第一个整数”即为两数的最大公约数。
代码示例
#include stdio.h
int main()
{int a, b;scanf(%d %d, a, b);int i;int gcd;gcd 1;for(i (ab?a: b); i 0; i--){if(a % i 0 b % i 0){gcd i;break;}}printf(gcd %d\n, gcd);return 0;
}另一种穷举原理
求出两数的所有公因子再把公因子累乘得到最大公约数。
代码示例
#include iostream
using namespace std;
int CommFactor2(int m, int n);
int main()
{int a, b;cin a b;cout 这两个数的最大公约数为 CommFactor2(a,b) endl;return 0;
}
int CommFactor2(int m,int n)
{int i;int factor 1;for (i2;imin;i){while(m % i 0 n % i 0) //这里不能用if语句因为可能会有重复的公因子{factor factor * i;m m / i;n n / i;}}return factor;
}辗转相除法
辗转相除法又称欧几里得算法。辗转相除法基于如下原理两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。表示gcd(a,b) gcd(b,a mod b) (ab) 代码示例
#include stdio.h
int main(int argc, const char* argv[])
{int a,b,temp;scanf(%d %d, a, b);while (b ! 0){temp a % b;a b;b temp;}printf(gcd %d\n, a);return 0;
}更相减损法
更相减损法又称辗转相减法。更相减损法出自《九章算术》“可半者半之不可半者副置分母、子之数以少减多更相减损求其等也。以等数约之。”(原本是为了约分而设计的)
具体方法为两个数之间大的数字减小的数字之后将得到的差作为减数较小的数作为被减数再次相减直到与所得的差相同此时的差即为两个数之间的最大公约数。
用(ab)表示a和b的最大公因数有结论(ab)(ak*ab)其中a、b、k都为自然数。
基于上面的原理就能实现我们的迭代相减法(7814)(6414)(5014)(3614)(2214)(814)(86)(26)(24)(22)(02)2
代码示例
#includeiostream
using namespace std;
int gcd(int a, int b)
{while(a ! b)if(a b) a - b;else b - a;return a;
}
int main(){int m,n;cinmn;coutgcd:gcd(m,n)endl;return 0;
}Stein算法
Stein算法是针对欧几里德算法在对大整数进行运算时需要试商导致增加运算时间的缺陷而提出的改进算法。
欧几里德算法是计算两个数最大公约数的传统算法无论从理论还是从实际效率上都是很好的。但是却有一个致命的缺陷这个缺陷在素数比较小的时候一般是感觉不到的只有在大素数时才会显现出来一般实际应用中的整数很少会超过64位当然现在已经允许128位了对于这样的整数计算两个数之间的模是很简单的。对于字长为32位的平台计算两个不超过32位的整数的模只需要一个指令周期而计算64位以下的整数模也不过几个周期而已。但是对于更大的素数这样的计算过程就不得不由用户来设计为了计算两个超过64位的整数的模用户也许不得不采用类似于多位数除法手算过程中的试商法这个过程不但复杂而且消耗了很多CPU时间。对于现代密码算法要求计算128位以上的素数的情况比比皆是比如说RSA加密算法至少要求500bit密钥长度设计这样的程序迫切希望能够抛弃除法和取模。
Stein算法很好的解决了欧几里德算法中的这个缺陷Stein算法只有整数的移位和加减法。下面就来说一下Stein算法的原理
若a和b都是偶数则记录下公约数2然后都除2即右移1位若其中一个数是偶数则偶数除2因为此时2不可能是这两个数的公约数了若两个都是奇数则a |a-b|b min(a,b)因为若d是a和b的公约数那么d也是|a-b|和min(a,b)的公约数
这里对3.进行简单的证明
不妨设奇数ABA和B的公约数为X即AjXBkX其中jk均为正整数且jk。
A−B(j−k)X
因为jk均为整数所以X也是A-B的公约数。
min(A,B)B
所以A-B与min(A,B)公约数相同因为AB都是奇数所以A-B必然是偶数偶数又可以二除移位了。代码示例1
#includeiostream
using namespace std;
int SteinGCD(int a, int b) {if (a b) { int t a; a b; b t; }if (b 0) return a;if ((a 1) 0 (b 1) 0)return SteinGCD(a 1, b 1) 1;else if ((a 1) 0 (b 1) ! 0)return SteinGCD(a 1, b);else if ((a 1) ! 0 (b 1) 0)return SteinGCD(a, b 1);elsereturn SteinGCD(a - b, b);
}
int main()
{int m,n;cinmn;coutgcd:SteinGCD(m,n)endl;return 0;
}代码示例2
#includeiostream
using namespace std;
int gcd(int u, int v)
{if (u 0) return v;if (v 0) return u;if (~u 1){if (v 1)return gcd(u 1, v);elsereturn gcd(u 1, v 1) 1;}if (~v 1)return gcd(u, v 1);if (u v)return gcd((u - v) 1, v);return gcd((v - u) 1, u);
}
int main()
{int m,n;cinmn;coutgcd:gcd(m,n)endl;return 0;
}Stein算法非递归方式
代码示例
#includeiostream
using namespace std;
int SteinGCD(int a, int b) {int acc 0;while ((a 1) 0 (b 1) 0) {acc;a 1;b 1;}while ((a 1) 0) a 1;while ((b 1) 0) b 1;if (a b) { int t a; a b; b t; }while ((a (a - b) 1) ! 0) {while ((a 1) 0) a 1;if (a b) { int t a; a b; b t; }}return b acc;
}
int main()
{int m,n;cinmn;coutgcd:SteinGCD(m,n)endl;return 0;
}库函数
__gcd(a,b)——库algorithm
注意gcd前面有两个下划线
gcd(a,b)——库numeric
注意仅作扩展如无必要不要使用
位运算
利用位运算的特性将两数交换改成位运算。 inline可加可不加。我实际试验中在1e8次执行后加与不加的时间差在80ms左右而两者本来的运行时间均在3000ms上下即差别不大
代码示例
inline int gcd(int a, int b)
{while(b ^ a ^ b ^ a % b); return a;
}利用取模特点
很快几乎与__gcd(a,b)的时间一致
代码示例
int gcd(int a, int b){if(!a || !b)return max(a, b);for(int t; t a % b; a b, b t);return b;
}以上方法都为最大公约数的求法若要求最小公倍数利用关系计算即可。
迭乘法(求最小公倍数)
由公倍数的定义出发如果一个数k是a和b的公倍数那么k可以表示成 a*m或 b*n而当(a*m) % b 0时k是最小公倍数
代码示例
#includestdio.h
int main(){int a,b;scanf(%d %d, a, b);int i 1;while((a*i) % b ! 0){i;}printf(最小公倍数是%d\n, a * i);return 0;
}参考博文
https://blog.csdn.net/Hsuesh/article/details/111992593
https://blog.csdn.net/ly_6699/article/details/90719315
https://blog.csdn.net/JH13thpig/article/details/124362053
https://blog.csdn.net/weq2011/article/details/127953257
https://blog.csdn.net/Holmofy/article/details/76401074
https://blog.csdn.net/wyd_333/article/details/126111037
