Logo

Programming-Idioms

  • D
  • Scheme
  • Dart

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.

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;
}
x = a.lcm(b);

extension LCM on int {
  int lcm(int other) => (this * other) ~/ this.gcd(other);
}
import std.numeric: gcd
uint x = (a * b) / gcd(a, b);
#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);

New implementation...
< >
deleplace