## Posted By

Scooter on 05/24/08

# Euclid's Algorithm

/ Published in: PHP

`<?php    /*    PHP Mathematics Library - Euclid's Algorithm        Copyright (c) 2008, reusablecode.blogspot.com; some rights reserved.        This work is licensed under the Creative Commons Attribution License. To view    a copy of this license, visit http://creativecommons.org/licenses/by/3.0/ or    send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California    94305, USA.    */     // Determine the greatest common divisor of two numbers using Euclid's algorithm.    function gcd(\$a, \$b)    {        \$a = abs(\$a);        \$b = abs(\$b);         if (\$a == 0)        {            return \$b;        }        elseif (\$b == 0)        {            return \$a;        }        elseif (\$a > \$b)        {            return gcd(\$b, \$a % \$b);        }        else        {            return gcd(\$a, \$b % \$a);        }    }     // Determine the least common multiple of two numbers using Euclid's algorithm.    function lcm(\$a, \$b)    {        \$a = abs(\$a);        \$b = abs(\$b);         if (\$a > \$b)        {            return (\$b / gcd(\$a, \$b)) * \$a;        }        else        {            return (\$a / gcd(\$a, \$b)) * \$b;        }    }?>`

Posted By: toddnestor on February 13, 2015

This was probably published a long time ago, but I happened to come across it today.

The gcd function made me curious, I would think this would be easier:

``` function GreatestCommonFactor( \$m, \$n ) { \$r = \$m % \$n;```

``` if( \$r != 0 ) \$n = GreatestCommonFactor( \$n, \$r ); return \$n; ```

```} ```

Or if you wanted something to double check that it is positive integers being input: ``` function GreatestCommonFactor( \$m, \$n ) { if( !isint( \$m ) || !isint( \$n ) || \$m<=0 || \$n<=0 ) return false;```

``` \$r = \$m % \$n; if( \$r != 0 ) \$n = GreatestCommonFactor( \$n, \$r ); return \$n; ```

```} ```

Posted By: toddnestor on February 13, 2015

apparently it doesn't let you edit your own comments, wasn't sure how the formatting would turn out, and that looks horrible :) however you should be able to see what I was writing.