CODEWITHSUNDEEP
javascript
user3371104
user3371104

Reputation: 269

Trying to find factors of a number in JS

I am just starting JS, and understand the concept of finding a factor. However, this snippet of code is what I have so far. I have the str variable that outputs nothing but the first factor which is 2. I am trying to add each (int) to the str as a list of factors. What's the wrong in below code snippet?

function calculate(num) {
    var str = "";
    var int = 2;
    if (num % int == 0) {
        str = str + int;
        int++;
    } else {
        int++;
    }
    alert(str);
}

calculate(232);

Upvotes: 20

Views: 53894

Answers (14)

Abdur Rahman
Abdur Rahman

Reputation: 43

We don't have to loop till end of the given number to find out all the factors. We just have to loop till reaching the given number's squareroot. After that point we, can figure out the rest of the factors by dividing the given number with the already found factors.

There is one special case with this logic. When the given number has a perfect square, then the middle factor is duplicated. The special case is also handled properly in the below code.

const findFactors = function (num) {

    const startingFactors = []
    const latterFactors = []
    const sqrt = Math.sqrt(num)
    
    for (let i = 1; i <= sqrt; i++) {
        if (num % i == 0) {
            startingFactors.push(i)
            latterFactors.push(num / i)
        }
    }

    // edge case (if number has perfect square, then the middle factor is replicated, so remove it)
    if (sqrt % 1 == 0) startingFactors.pop()

    return startingFactors.concat(latterFactors.reverse())
}

Upvotes: 0

ferso
ferso

Reputation: 99

Using generators in typescript in 2021

function* numberFactorGenerator(number: number): Generator<number> {
  let i: number = 0;
  while (i <= number) {
    if (number % i === 0) {
      yield i;
    }
    i++;
  }
}
 console.log([...numberFactorGenerator(12)]); // [ 1, 2, 3, 4, 6, 12 ]

Upvotes: 2

Larry
Larry

Reputation: 1248

As an even more performant complement to @the-quodesmith's answer, once you have a factor, you know immediately what its pairing product is:

function getFactors(num) {
  const isEven = num % 2 === 0;
  const max = Math.sqrt(num);
  const inc = isEven ? 1 : 2;
  let factors = [1, num];

  for (let curFactor = isEven ? 2 : 3; curFactor <= max; curFactor += inc) {
    if (num % curFactor !== 0) continue;
    factors.push(curFactor);
    let compliment = num / curFactor;
    if (compliment !== curFactor) factors.push(compliment);
  }

  return factors;
}

for getFactors(300) this will run the loop only 15 times, as opposed to +-150 for the original.

Upvotes: 17

Guy
Guy

Reputation: 13286

UPDATED ES6 version:

As @gengns suggested in the comments a simpler way to generate the array would be to use the spread operator and the keys method:

const factors = number => [...Array(number + 1).keys()].filter(i=>number % i === 0);
console.log(factors(36));      //  [1, 2, 3, 4, 6, 9, 12, 18, 36]

ES6 version:

const factors = number => Array
    .from(Array(number + 1), (_, i) => i)
    .filter(i => number % i === 0)

console.log(factors(36));      //  [1, 2, 3, 4, 6, 9, 12, 18, 36]

https://jsfiddle.net/1bkpq17b/

  • Array(number) creates an empty array of [number] places

  • Array.from(arr, (_, i) => i) populates the empty array with values according to position [0,1,2,3,4,5,6,7,8,9]

  • .filter(i => ...) filters the populated [0,1,2,3,4,5] array to the elements which satisfy the condition of number % i === 0 which leaves only the numbers that are the factors of the original number.

Note that you can go just until Math.floor(number/2) for efficiency purposes if you deal with big numbers (or small).

Upvotes: 39

The Qodesmith
The Qodesmith

Reputation: 3375

@Moob's answer is correct. You must use a loop. However, you can speed up the process by determining if each number is even or odd. Odd numbers don't need to be checked against every number like evens do. Odd numbers can be checked against every-other number. Also, we don't need to check past half the given number as nothing above half will work. Excluding 0 and starting with 1:

function calculate(num) {
    
    var half = Math.floor(num / 2), // Ensures a whole number <= num.
        str = '1', // 1 will be a part of every solution.
        i, j;
    
    // Determine our increment value for the loop and starting point.
    num % 2 === 0 ? (i = 2, j = 1) : (i = 3, j = 2);
    
    for (i; i <= half; i += j) {
        num % i === 0 ? str += ',' + i : false;
    }

    str += ',' + num; // Always include the original number.
    console.log(str);
}

calculate(232);

http://jsfiddle.net/r8wh715t/

While I understand in your particular case (calculating 232) computation speed isn't a factor (<-- no pun intended), it could be an issue for larger numbers or multiple calculations. I was working on Project Euler problem #12 where I needed this type of function and computation speed was crucial.

Upvotes: 11

Rayne
Rayne

Reputation: 81

This got me an 85% on Codility (Fails on the upperlimit, over a billion).

Reducing the input by half doesn't work well on large numbers as half is still a very large loop. So I used an object to keep track of the number and it's half value, meaning that we can reduce the loop to one quarter as we work from both ends simultaneously. N=24 becomes: (1&24),(2&12),(3&8),(4&6)

function solution(N) {

    const factors = {};

     let num = 1;  
     let finished = false;
     while(!finished)
     {
         if(factors[num] !== undefined)
         {
             finished = true;
         }
         else if(Number.isInteger(N/num))
         {

          factors[num] = 0;
          factors[N/num]= 0;
         }
        num++
     }

    return Object.keys(factors).length;
}

Upvotes: 1

Lewis Nakao
Lewis Nakao

Reputation: 7372

Here's an optimized solution using best practices, proper code style/readability, and returns the results in an ordered array.

function getFactors(num) {
    const maxFactorNum = Math.floor(Math.sqrt(num));
    const factorArr = [];
    let count = 0;  //count of factors found < maxFactorNum.

    for (let i = 1; i <= maxFactorNum; i++) {
        //inserting new elements in the middle using splice
        if (num % i === 0) {
            factorArr.splice(count, 0, i);
            let otherFactor = num / i; //the other factor
            if (i != otherFactor) {
                //insert these factors in the front of the array
                factorArr.splice(-count, 0, otherFactor);
            }
            count++;
        }
    }

    //swapping first and last elements
    let lastIndex = factorArr.length - 1;
    let temp = factorArr[lastIndex];
    factorArr[lastIndex] = factorArr[0];
    factorArr[0] = temp;

    return factorArr;
}

console.log(getFactors(100));
console.log(getFactors(240));
console.log(getFactors(600851475143)); //large number used in Project Euler.

I based my answer on the answer written by @Harman

Upvotes: 0

Harman
Harman

Reputation: 155

here is a performance friendly version with complexity O(sqrt(N)). Output is a sorted array without using sort.

var factors = (num) => {
let fac = [], i = 1, ind = 0;

while (i <= Math.floor(Math.sqrt(num))) {
  //inserting new elements in the middle using splice
  if (num%i === 0) {
    fac.splice(ind,0,i);
    if (i != num/i) {
      fac.splice(-ind,0,num/i);
    }
    ind++;
  }
  i++;
}

//swapping first and last elements
let temp = fac[fac.length - 1];
fac[fac.length - 1] = fac[0];
fac[0] = temp;

// nice sorted array of factors
return fac;
};
console.log(factors(100));

Output: [ 1, 2, 4, 5, 10, 20, 25, 50, 100 ]

Upvotes: 2

mrded
mrded

Reputation: 5270

Below is an implementation with the time complexity O(sqrt(N)):

function(A) {
  var output = [];

  for (var i=1; i <= Math.sqrt(A); i++) {
    if (A % i === 0) {
      output.push(i);

      if (i !== Math.sqrt(A)) output.push(A/i);
    }
  }

  if (output.indexOf(A) === -1) output.push(A);

  return output;
}

Upvotes: 3

Swam Didam
Swam Didam

Reputation: 61

function calculate(num){
    var str = "0"   // initializes a place holder for var str
      for(i=2;i<num;i++){     
        var num2 = num%i;
        if(num2 ==0){       
            str = str +i; // this line joins the factors to the var str
        }
    }
    str1 = str.substr(1) //This removes the initial --var str = "0" at line 2
    console.log(str1) 
}
calculate(232);

//Output 2482958116

Upvotes: 0

Moob
Moob

Reputation: 16184

function calculate(num) {
    var str = "0";
    for (var i = 1; i <= num; i++) {
        if (num % i == 0) {
            str += ',' + i;
        }
    }
    alert(str);
}

calculate(232);

http://jsfiddle.net/67qmt/

Upvotes: 9

Vincent
Vincent

Reputation: 2777

I came looking for an algorithm for this for use in factoring quadratic equations, meaning I need to consider both positive and negative numbers and factors. The below function does that and returns a list of factor pairs. Fiddle.

function getFactors(n) {
  if (n === 0) {return "∞";} // Deal with 0
  if (n % 1 !== 0) {return "The input must be an integer.";} // Deal with non-integers

  // Check only up to the square root of the absolute value of n
  // All factors above that will pair with factors below that
  var absval_of_n = Math.abs(n),
      sqrt_of_n = Math.sqrt(absval_of_n),
      numbers_to_check = [];
  for (var i=1; i <= sqrt_of_n; i++) {
    numbers_to_check.push(i);
  }

  // Create an array of factor pairs
  var factors = [];
  for (var i=0; i <= numbers_to_check.length; i++) {
    if (absval_of_n % i === 0) {
      // Include both positive and negative factors
      if (n>0) {
        factors.push([i, absval_of_n/i]);
        factors.push([-i, -absval_of_n/i]);
      } else {
        factors.push([-i, absval_of_n/i]);
        factors.push([i, -absval_of_n/i]);
      }
    }
  }

  // Test for the console
  console.log("FACTORS OF "+n+":\n"+
              "There are "+factors.length+" factor pairs.");
  for (var i=0; i<factors.length; i++) {
    console.log(factors[i]);
  }

  return factors;
}

getFactors(-26);

Upvotes: 0

Peter Eskandar
Peter Eskandar

Reputation: 79

function factorialize(num) { 
 if(num === 0)
   return 1; 
 var arr = []; 
 for(var i=1; i<= num; i++){
   arr.push(i);
 } 
 num = arr.reduce(function(preVal, curVal){
   return preVal * curVal;
 });

  return num;
}

factorialize(5);

Upvotes: -1

user4520208
user4520208

Reputation: 

function factorialize(num) {
 var result = '';
  if( num === 0){
    return 1;
  }else{
    var myNum = [];

  for(i = 1; i <= num; i++){
    myNum.push(i);
    result = myNum.reduce(function(pre,cur){
      return pre * cur;
    });
  }
     return result;
    }
}

factorialize(9);

Upvotes: 0

Related Questions