Least Common Multiple in PHP

LCM(a,b) is the smallest integer divisible to both a and b from wikipedia. It can actually be simplified using prime factorization which denotes from wikipedia as:

The unique factorization theorem says that every positive integer greater than 1 can be written in only one way as a product of prime numbers. The prime numbers can be considered as the atomic elements which, when combined together, make up a composite number.

In order to find the LCM we will need to compute for its greatest common divisor defined 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

Assuming b is not equal to zero, we get the formula as

lcm(a,b) = a *b / gcd(a,b)

Converting it to PHP code we get:

//lcm(a,b) = floor(a*b)/gcd(a,b)
function lcm($a, $b) { 
	return ( $a / gcd($a,$b) ) * $b; 

Get the PHP code for GCD here.

Leave a Reply