Greatest Common Divisor in PHP

The greatest common divisor is defined in wikipedia as

gcd(a,0) = a

gcd(a,b) = gcd(a-b,b) , if a>b

gcd(a,b) = gcd(a,b-a) , if b>a

 

Converting this to php code we get:

// http://en.wikipedia.org/wiki/Greatest_common_divisor
// gcd(a,0) = a
// gcd(a,b) = gcd(b,a%b)
function gcd($a,$b){
	return ($b == 0) ? $a : gcd($b,$a%$b); 
}

 

 

1 Comment
Leave a Reply