How to return all the divisors from a big integer?-CodePudding

I understand the concept of how to return all the divisors from an given integer. However, when it gets to the big integers, nothing gets return:

function divisors(n,res=[]) {
  for (let i = 1; i <= n; i  ) !(n%i) && res.push(i);
  return res;
}

console.log(divisors(4)); // [ 1, 2, 4 ]
console.log(divisors(9)); // [ 1, 3, 9 ]
console.log(divisors(12)); // [ 1, 2, 3, 4, 6, 12 ]
console.log(divisors(975179493674)); // ?????
console.log(divisors(27550356289)); // ?????

The next logical step is to minimize the iteration amount by taking the square root of the given integer n in the for loop. This works and partially return some divisors but it didn't return all the divisors from each integers.

function divisors(n,res=[]) {
  for (let i = 1; i <= Math.floor(Math.sqrt(n)); i  ) {
    !(n%i) && res.push(i)
  }
  return res
}

console.log(divisors(4)); // [ 1, 2 ]
console.log(divisors(9)); // [ 1, 3 ]
console.log(divisors(12)); // [ 1, 2, 3 ]
console.log(divisors(975179493674)); // [ 1, 2, 97, 194 ]
console.log(divisors(27550356289)); // [ 1, 165983 ]

I just can't quite wrap my head around it. Any help or pointers will be greatly appreciated.

CodePudding user response：

Having found all the divisors less than or equal to the square root of the input, you can then divide the input by those numbers to get the rest of the divisors:

function divisors(n,res=[]) {
  for (let i = 1; i <= Math.floor(Math.sqrt(n)); i  ) {
    if (n%i == 0) { res.push(i) }
  }
  let len = res.length;
  // if n is a square, don't include the square root twice
  if (res[len-1] * res[len-1] == n) len--;
  for (i = len - 1; i >= 0; i--) { res.push(n / res[i]) }
  return res
}

console.log(divisors(4)); // [ 1, 2, 4 ]
console.log(divisors(9)); // [ 1, 3, 9 ]
console.log(divisors(12)); // [ 1, 2, 3, 4, 6, 12 ]
console.log(divisors(975179493674)); // [ 1, 2, 97, 194, 5026698421, 10053396842, 487589746837, 975179493674 ]
console.log(divisors(27550356289)); // [ 1, 165983, 27550356289 ]

CodePudding user response：

It makes sense to distinguish several similar but different problems here:

(1) To check whether a number N is a prime number or not, you can stop searching for possible divisors when you've reached its square root. That's because if N == x * y, and x > sqrt(N), then y < sqrt(N), so you would have found y before finding x.
As an example with concrete numbers: to check whether 11 is prime, you can stop searching after checking that 11 % 2 != 0 and 11 % 3 != 0 (because sqrt(11) < 4). If any of 4, 5, 6, ... were divisors of 11, then there'd be a corresponding divisor 11/4 or 11/5 or 11/6 etc, all of which are smaller than sqrt(11), so you would have found them before.

(2) To find all prime factors of a number N, you can't simply stop searching at sqrt(N). In contrast with case (1): if you only want to test whether 10 is prime, you can stop searching for divisors after checking 3 == floor(sqrt(10)) (and you would have found 2 at that point, proving that 10 is not prime), whereas if your task is to find all prime factors, you need to somehow find 5 as well, and 5 > sqrt(10).

One way to accomplish that is to keep dividing N by each factor that you find, so you'd have something like:

function primeFactors(n,res=[]) {
  for (let i = 2; i <= Math.floor(Math.sqrt(n)); ) {
    let candidate = Math.floor(n / i);
    if (candidate * i === n) {
      res.push(i);
      n = candidate;
    } else {
      i  ;
    }
  }
  res.push(n);
  return res;
}

Note that this uses candidate * i === n instead of n % i === 0 because multiplications are much faster than divisions. Since we already have the n / i division (and can't avoid that in this approach), we can at least replace the second n % i division with that multiplication.
Similarly, you could improve performance further if you replaced the loop's condition i <= Math.floor(Math.sqrt(n)) with i*i <= n. Or even better, reusing the work we've already done: if (candidate < i) break;.

(3) To find all divisors (both prime factors and composite divisors), you can approach the problem from several directions:
The simplest is probably to do what @Nick's answer suggests: try all candidates i from 1 to sqrt(N), and whenever you find one, add both i and n / i to the list.
As a minor improvement to that, you could start at i = 2, and always add 1 and n to the list without checking (because every integer is divisible by 1 and by itself).

An alternative that's probably faster, but also more complicated to implement, is to find the prime factors first (see (2)), and then build the set of all divisors as the powerset of the prime factors. For example, if you find that the prime factors are [2, 3, 5], then the set of divisors is [1, 2, 3, 5, 2*3, 2*5, 3*5, 2*3*5]. (Note that this will need some deduplication when some prime factors occur more than once.)

If performance is really important, there's more you could do. For example, you could cache prime numbers you've found, and on subsequent invocations only check those as possible divisors.
A very simple step in this direction would be to special-case i=2, and then check only odd candidates (3, 5, 7, ...) afterwards. That simple trick would save about half the work!
One can even go as far as getting rid of expensive divisions entirely at the cost of spending some more memory to keep track of the next multiple of each prime that needs to be checked... but that's getting a bit far from your original question! Before getting too carried away with optimizations, I'd like to point out that for a single invocation, even for an input like 975179493674, any such tuning isn't worth the effort: you'd save a couple of milliseconds of execution time, but it would cost at least several minutes to implement. However, if this happens to be a performance-critical core part of an application, then it provides quite some room for investing implementation effort in order to save execution time.