0

Hi everyone

I have to finish the following task:

Define LCM(N)as the Least common multiple of 1, 2, 3, ..., N. Find LCM(N) mod 10^8.

This is an example: LCM(27) = 13433200

My problem is that the function leastCommonMultiple(min, max) returns in some cases infinit. I've got so far already:

function LCM(N) {
    return leastCommonMultiple(1, N) % Math.pow(10,8);
}

function leastCommonMultiple(min, max) {
    function range(min, max) {
        var arr = [];
        for (var i = min; i <= max; i++) {
            arr.push(i);
        }
        return arr;
    }

    function gcd(a, b) {
        return !b ? a : gcd(b, a % b);
    }

    function lcm(a, b) {
        return (a * b) / gcd(a, b);   
    }

    var multiple = min;
    range(min, max).forEach(function(n) {
        multiple = lcm(multiple, n);
    });

    return multiple;
}

It would be coool if somebody has good skills in Maths an JS and can help me with this problem.

Greetings :)

G43beli
  • 3,835
  • 4
  • 21
  • 28
  • I think this has already been asked and answered here. http://stackoverflow.com/questions/31302054/how-to-find-the-least-common-multiple-of-a-range-of-numbers – David Pine Nov 17 '15 at 12:57
  • not exactly, I saw this post too. but when I have for example leastCommonMultiple(1, 10000) -> the function returns infinit. – G43beli Nov 17 '15 at 13:06
  • @G43beli Do you understand how big a number the LCM of all numbers between 1..10000 will be? It will have several hundreds digits (if I am not mistaken). `Infinity` in JS means that the number is so big that JS cannot represent it. The problem is that you cannot separately calculate LCM(N) and then the mod. You have to combine both operations and perform them in paralel to avoid big numbers. – Sulthan Nov 17 '15 at 13:09
  • @Sulthan yeah exactyl that's my plan. I tried that but i couldnt find the right way yet. Because in every case I have to find de LCM with mod 10^8. – G43beli Nov 17 '15 at 13:16
  • See http://stackoverflow.com/questions/24574299/lcm-of-n-numbers-modulo-1000000007 – Sulthan Nov 17 '15 at 13:25

0 Answers0