# Programming-Idioms

This language bar is your friend. Select your favorite languages!

# Idiom #75 Compute LCM

Compute the least common multiple x of big integers a and b. Use an integer type able to handle huge numbers.

``extension=gmp``
``````\$gcd = gmp_lcm(\$a, \$b);
echo gmp_strval(\$gcd);``````
``#include <gmp.h>``
``````mpz_t _a, _b, _x;
mpz_init_set_str(_a, "123456789", 10);
mpz_init_set_str(_b, "987654321", 10);
mpz_init(_x);

mpz_lcm(_x, _a, _b);
gmp_printf("%Zd\n", _x);``````
``#include <numeric>``
``auto x = std::lcm(a, b);``
``````int gcd(int a, int b)
{
while (b != 0)
{
int t = b;
b = a % t;
a = t;
}
return a;
}

int lcm(int a, int b)
{
if (a == 0 || b == 0)
return 0;
return (a * b) / gcd(a, b);
}

int x = lcm(140, 72);``````
``import std.numeric: gcd``
``uint x = (a * b) / gcd(a, b);``
``````x = a.lcm(b);

extension LCM on int {
int lcm(int other) => (this * other) ~/ this.gcd(other);
}``````
``````x = lcm(a, b);

int lcm(int a, int b) => (a * b) ~/ gcd(a, b);

int gcd(int a, int b) {
while (b != 0) {
var t = b;
b = a % t;
a = t;
}
return a;
}``````
``````defmodule BasicMath do
def gcd(a, 0), do: a
def gcd(0, b), do: b
def gcd(a, b), do: gcd(b, rem(a,b))

def lcm(0, 0), do: 0
def lcm(a, b), do: (a*b)/gcd(a,b)
end``````
``````gcd(A,B) when A == 0; B == 0 -> 0;
gcd(A,B) when A == B -> A;
gcd(A,B) when A > B -> gcd(A-B, B);
gcd(A,B) -> gcd(A, B-A).

lcm(A,B) -> (A*B) div gcd(A, B).``````
``import "math/big"``
``````gcd.GCD(nil, nil, a, b)
x.Div(a, gcd).Mul(x, b)``````
``````x = lcm a b
``````
``````const gcd = (a, b) => b === 0 ? a : gcd (b, a % b)
let x = (a * b) / gcd(a, b)``````
``import java.math.BigInteger;``
``````BigInteger a = new BigInteger("123456789");
BigInteger b = new BigInteger("987654321");
BigInteger x = a.multiply(b).divide(a.gcd(b));``````
``(setf x (lcm a b))``
``````sub gcd {
my (\$x, \$y) = @_;
while (\$x) { (\$x, \$y) = (\$y % \$x, \$x) }
\$y
}

sub lcm {
my (\$x, \$y) = @_;
(\$x && \$y) and \$x / gcd(\$x, \$y) * \$y or 0
}``````
``````sub lcm {
use integer;
my (\$x, \$y) = @_;
my (\$f, \$s) = @_;
while (\$f != \$s) {
(\$f, \$s, \$x, \$y) = (\$s, \$f, \$y, \$x) if \$f > \$s;
\$f = \$s / \$x * \$x;
\$f += \$x if \$f < \$s;
}
\$f
}``````
``import math``
``x = math.lcm(a, b)``
``from math import gcd``
``x = (a*b)//gcd(a, b)``
``x = a.lcm(b)``
``````extern crate num;

use num::Integer;
use num::bigint::BigInt;``````
``let x = a.lcm(&b);``

deleplace