首页 > 代码库 > 求最大公约数的几种算法分析

求最大公约数的几种算法分析

题目——求两个整数的最大公约数

思路1、穷举算法

 
public static voidmain(String[] args) throws IOException {
Scannerscanner = new Scanner(System.in);
inta = scanner.nextInt();
intb = scanner.nextInt();
System.out.println("开始时间是"+System.currentTimeMillis());
System.out.println(gcd(a,b));
System.out.println("结束时间是"+System.currentTimeMillis());
}
 
private static intgcd(int a, int b) {
intgcd = 1;
for(int i = 2; i <=a  && i<=b;i++) {
if(a%i == 0 && b%i == 0) {
gcd= i;
}
}
returngcd;
}


验证——

用两个数字来进行验证,同时计算开始计算前的时刻和计算完毕的时刻,可以得到该算法需要的运行时间。

3450012

2100324

开始时间是1401859016757

12

结束时间是1401859016775

 

明显,该算法的复杂度是O(N),所需要的运行时间是18毫秒。比较长。需要改进。

思路2——改进后的穷举算法

这里假设,数字ab大,数字a的除数不可能比a/2还大。因此,我们从a/2开始穷举找起,会更快。但是考虑到一种情况就是,数字b有可能是a的除数。所以,改进后的算法如下——

private static intgcd(int a, int b) {
intgcd = 1;
intm=0,n =0;
//m存储较大值,n存储较小值
if(a>b){
m= a;
n= b;
}else{
m= b;
n= a;
}
if(m%n == 0) {
gcd= n;
returngcd;
}
 
for(int i = n/2; i>=1; i--) {
if(m%i == 0 && n%i == 0) {
gcd= i;
break;
}
}
returngcd;
}


验证——

3450012

2100324

开始时间是1401859092824

12

结束时间是1401859092834

可以看出,执行时间上明显减少了,只需要10毫秒。假如a>b,实际上这个for循环只是最多执行n/2次,比第一个完全穷举要缩短一半的时间。

尽管它的算法复杂度依然是O(N)

但是,第二个算法只是改进了的穷举算法,效率依然不够高。比之更好些的一个算法是

思路3——进欧几里算法

这是上世纪的一个数学家进欧几里得发现的一个算法。用gcd(m,n)来表示整数m,n的最大公约数,则算法的定义为:

  • 如果m%n == 0,那么gcd(m,n)就是n;
  • 否则,gcd(m,n)就是gcd(n,m%n)

private static intgcd(int a, int b) {
intm=0,n =0;
//m存储较大值,n存储较小值
if(a>b){
m= a;
n= b;
}else{
m= b;
n= a;
}
if(m%n == 0) {
returnn;
}else{
returngcd(n,m%n);
}
}
 


验证——

3450012

2100324

开始时间是1401858942252

12

结束时间是1401858942252

可以看到,进欧几里的算法比前两个算法快很多,执行时间在1毫秒以内。这是很不错的效率。