一 暴力枚举法
原理:试图寻找一个合适的整数i,看看这个整数能否被两个整形参数numberA和numberB同时整除。这个整数i从2开始循环累加,一直累加到numberA和numberB中较小参数的一半为止。循环结束后,上一次寻找到的能够被两整数整除的最大i值,就是两数的最大公约数。
int getGreatestCommonDivisor(int numberA, int numberB) { ||numberB < ) { ; } || numberB <= ) { ; } int max = numberA > numberB ? numberA : numberB; int min = numberA > numberB ? numberB : numberA; ) { return min; } ; ; ; i <= min/; i++) { ) && (numberB % i == )) { ret = i; } } return ret; }
二 辗转相除法(欧几里得算法)
原理:两个正整数a和b(a > b),它们的最大公约数等于a除于b的余数c和b之间的最大公约数。比如10和25,25除以10余数5,那么10和25的最大公约数,等于10和5的最大公约数。然后以此类推,直到两个数可以整除,或者其中一个数减小到1为止。
缺陷:当两个整形数较大时,a % b取模运算的性能比较低。
int gcd(int a, int b) { ) { return b; } else { return gcd(b, a%b); } } int getGreatestCommonDivisor(int numberA, int numberB) { ||numberB < ) { ; } || numberB <= ) { ; } int max = numberA > numberB ? numberA : numberB; int min = numberA > numberB ? numberB : numberA; ) { return min; } else { return gcd(max, min); } }
三 更相减损术
原理:两个正整数a和b(a > b),它们的最大公约数等于a - b的差值c和较小数b的最大公约数。
缺陷:更相减损术的运算次数肯定远大于辗转相除法。特别是当两数相差比较大,相减的次数很大。
int gcd(int a, int b) { if (a == b) { return a; } if (a > b) { return gcd(a-b, b); } else { return gcd(b-a, a); } } int getGreatestCommonDivisor(int numberA, int numberB) { ||numberB < ) { ; } || numberB <= ) { ; } int max = numberA > numberB ? numberA : numberB; int min = numberA > numberB ? numberB : numberA; ) { return min; } else { return gcd(max, min); } }
四 辗转相除法和更相减损术相结合
原理:当a和b均为偶数,gcb(a, b) = 2 * gcb(a/2, b/2) = 2 * gcb(a>>1, b>>1) = gcb(a>>1, b>>1) << 1
当a为偶数,b为奇数,gcb(a, b) = gcb(a/2, b) = gcb(a>>1, b)
当a为奇数,b为偶数,gcb(a, b) = gcb(a, b/2) = gcb(a, b>>1)
当a和b均为奇数,先用更相减损术运算一次,gcb(a, b) = gcb(b, a-b),此时a-b是偶数,用上面的公式
说明:移位运算的性能非常快,a/2 转换成a>>1,a * 2 = a << 1
和1做&操作,判断奇偶:结果为真奇数,结果为假偶数
int gcd(int a, int b) { if (a == b) { return a; } )) && (!(b&))) // a和b均为偶数 { , b>>) << ; } )) && (b&)) // a偶数,b奇数 { , b); } ) && (!(b&))) // a奇数,b偶数 { ); } else // a和b均为奇数 { if (a > b) { return gcd(a-b, b); } else { return gcd(b-a, a); } return gcd(a-b, b); } } int getGreatestCommonDivisor(int numberA, int numberB) { ||numberB < ) { ; } || numberB <= ) { ; } int max = numberA > numberB ? numberA : numberB; int min = numberA > numberB ? numberB : numberA; ) { return min; } else { return gcd(max, min); } }