只用一行代码求出最大公约数js版

此方法主要用到这样一个定理：a和b的公约数==b和a%b的公约数==a%b和b%(a%b)的公约数…………；

另外要知道.a和0的公约数==a;

直接看代码吧(之前写的时候先判断是否为质数实在是多此一举，并且产生了很多麻烦，比如下面u会输出1)

普通版：

	//求最大公约数
	function Mgn(num1,num2){
		var temp=0;
		while(num2!=0){		//当num2==0时,最大公约数为num1
			temp=num1%num2;
			num1=num2;
			num2=temp;
		}
		return num1;
	}
	var p=Mgn(0,-15);
	var q=Mgn(45,81);
	var u=Mgn(-15,3);
	console.log(p);//-15
	console.log(q);//9
	console.log(u);//3

改进版(极简版)：

	function Mgn(num1,num2){
		return num2!=0 ? Mgn(num2,num1%num2) : num1;//整个函数的实现只需要一行代码
	}
	var p=Mgn(0,-15);
	var q=Mgn(45,81);
	var u=Mgn(-15,3);
	console.log(p);//-15
	console.log(q);//9
	console.log(u);//3

??

之前的代码(错误且低效的写法！！！！)：

//判断是否为质数

function isZhiShu(num){

for(var i=2;i<Math.sqrt(num);i++){

if (num%i==0) { return false;}

}

return true;

}

?

//求最大公约数

function Mgn(num1,num2){

if (num1==0||num2==0) {return num1==0 ? num2:num1;}//解决0的问题

if (isZhiShu(~~num1)&&isZhiShu(~~num2)) {return 1}//如果两个数都为质数就不做下一步处理

var temp=0;

while(num2!=0){//当num2==0时,最大公约数为num1

temp=num1%num2;

num1=num2;

num2=temp;

}

return num1;

}

var p=Mgn(0,-15);

var q=Mgn(45,81);

var u=Mgn(-15,3);

console.log(p);//-15

console.log(q);//9

console.log(u);//1,这里出错

?

只用一行代码求出最大公约数js版

原文：http://cobain-li.iteye.com/blog/2296959