34 lines
541 B
Plaintext
34 lines
541 B
Plaintext
function factors(n) {
|
|
var f = {};
|
|
|
|
for var i = 2; n > 1; i++ {
|
|
while n % i == 0 {
|
|
n /= i;
|
|
f[i] = f[i] != nil ? f[i] + 1 : 1;
|
|
}
|
|
}
|
|
|
|
return f;
|
|
}
|
|
|
|
function GCD(n, k) {
|
|
let f1 = factors(n);
|
|
let f2 = factors(k);
|
|
|
|
let fs = map(f1, function(factor, multiplicity) {
|
|
let m = f2[factor];
|
|
return m == nil ? 0 : min(m, multiplicity);
|
|
});
|
|
|
|
let rfs = {};
|
|
foreach(fs, function(k, v) {
|
|
rfs[sizeof rfs] = pow(k, v);
|
|
});
|
|
|
|
return reduce(rfs, 1, function(x, y) { return x * y; });
|
|
}
|
|
|
|
function LCM(n, k) {
|
|
return n * k / GCD(n, k);
|
|
}
|