javascript - Find the multiple of n numbers within given range -

how can find number of multiple n numbers(as array input) range 1 k, 1 < k < 10⁸ , 3 ≤ n < 25.

function findnumberofmultiples(inputarray, maxsize) {        var count = 0;     var temparray = [];     (var i=0; i<maxsize; i++){         temparray[i] = 0;     }      (var j=0; j<inputarray.length; j++) {         (var i=1; i<=maxsize; i++) {             if (i % inputarray[j]) {                 temparray[i-1] = 1;             }         }     }      (var i=0; i<maxsize; i++) {         if (temparray[i]==1) {             count++;         }     }  return count; } 

the above program fails large number k. example, if inputarray = [2,3,4] , maxsize(k) 5,

• multiple of 2 2,4
• multiple of 3 3
• multiple of 4 4

so total number of mutiple of 2 or 3 or 4 3 in range 1 5

you can solve in o(n^2) n number of elements in array.

let have 2 element in array [a1,a2] , range k

your answer = >

  k/a1 + k/a2 - k/lcm(a1,a2) // because added them in both a1 , a2 

so if have a1,.....ax elements, answer be

k/a1+.....k/ax - k/lcm(ai,aj) (you have replace i,j (n*n-1)/2 combinations.  

you have k/lcm(ai,aj) o(n^2) times ((n*n-1)/2 time precise). algorithm complexity o(n^2) (there log(min(ai,aj)) factor not make difference overall complexity). work k depends on innput array size.

 public int combinations(int k, int[] input){     int total = 0;     for(int i=0;i<input.length;i++){         total  =  total + math.floor(k/input[i]);     }     for(int i=0;i<input.length;i++){         for(int j=i+1;j<input.length;j++){             if(i!=j){                 int lcm =lcmfind(input[i], input[j]);                 total = total - math.floor(k/lcm);             }         }     }     return total; } 

the test case have provided: