Return to Question

I am trying to sort all the divisors of a given number in the most efficient way.

Below is my code for sorting the divisors:

num = 100;
end = num ** (1 / 2);
divisors = [1];
disvisorPairs = [];
pairCount = 0;
for (var i = 2; i <= end; i++) {
  if (num % i == 0) {
    divisors.push(i);
    pair = num / i;
    if (pair != i) {
      pairCount++;
      disvisorPairs.push(pair);
    }
  }
}
for (var i = pairCount - 1; i >= 0; i--) {
  divisors.push(disvisorPairs[i]);
}
if (num != 1) divisors.push(num);
console.log(divisors);

• Is there anything else I can do to increase the performance of my code?
• Is there a data structure other than arrays that can possibly sort the the divisors in constant time?

I am trying to sort all the divisors of a given number in the most efficient way.

Below is my code for sorting the divisors:

num = 100;
end = num ** (1 / 2);
divisors = [1];
disvisorPairs = [];
pairCount = 0;
for (var i = 2; i <= end; i++) {
  if (num % i == 0) {
    divisors.push(i);
    pair = num / i;
    if (pair != i) {
      pairCount++;
      disvisorPairs.push(pair);
    }
  }
}
for (var i = pairCount - 1; i >= 0; i--) {
  divisors.push(disvisorPairs[i]);
}
if (num != 1) divisors.push(num);
console.log(divisors);

• Is there anything else I can do to increase the performance of my code?
• Is there a data structure other than arrays that can possibly sort the the divisors in constant time?

I am trying to sort all the divisors of a given number in the most efficient way. This is my first time trying to make my code to be most efficient.

Below is my code for finding divisors:

num = 36;
end = num ** (1 / 2); 
divisors = [1];
for (var i = 2; i <= end; i++) {
  if (num % i == 0) { 
    divisors.push(i); 
    pair = num / i;
    if (pair != i) divisors.push(pair);
  }
}
divisors.push(num);
console.log(divisors);

This above code doesn't sort all my divisors. I try to sort them using two methods.

Sorting Method1 - creating two separate arrays for the first divisor and its pair and then merging them together

Time Complexity - O(sqrt(num)) + O(pairCount) => O(sqrt(num))

num = 36;
end = num ** (1 / 2);
divisors = [1];
divisorsPair = [];
PairCount = 0;
for (var i = 2; i <= end; i++) {
  if (num % i == 0) {
    divisors.push(i);
    pair = num / i;
    if (pair != i) {
      PairCount++;
      divisorsPair.push(pair);
    }
  }
}
for (var i = PairCount - 1; i >= 0; i--) {
  divisors.push(divisorsPair[i]);
}
divisors.push(num);
console.log(divisors);

Sorting Method2 - Just sort() the array after pushing all the divisors in a single array

Time Complexity - O(sqrt(num) + num log(num) ) => O(num log(num))

num = 36;
end = num ** (1 / 2);
divisors = [1];
for (var i = 2; i <= end; i++) {
  if (num % i == 0) {
    divisors.push(i);
    pair = num / i;
    if (pair != i) divisors.push(pair);
  }
}
divisors.sort((a, b) => a - b);
divisors.push(num);
console.log(divisors);

Assuming push() has O(1) complexity without any memory fragmentation issues, then why does the second method seems to be considered a better practice over the first method when first one clearly has lesser time complexity?

Also, my gut feeling tells me that I can further optimize the method1 by inserting the divisor directly into some data structure in constant time without breaking the sort order or shifting the memory values. Maybe by using a linked list or dynamic memory allocation and pointers. I guess linked list may not be the best solution as we may have to traverse from the first element all the time.

Maybe the most efficient way will be to find out first how many total divisors the given number will have and then store the divisors directly into the right index to get a sorted array. But the formula for finding total divisors using prime factorization seems to just increase the code redundancy.

In this case is it really possible to insert all the divisor into an array or any other special data structure in constant time. I will highly appreciate if anyone can tell me the best efficient approach to sort the divisors for this problem with a short explanation about the idea behind it.

Please suggest any C approach too with a short explanation of the idea behind it, if it can be faster, which can sort my divisors in constant time for this particular problem.

I am trying to sort all the divisors of a given number in the most efficient way.

Below is my code for sorting the divisors:

num = 100;
end = num ** (1 / 2);
divisors = [1];
disvisorPairs = [];
pairCount = 0;
for (var i = 2; i <= end; i++) {
  if (num % i == 0) {
    divisors.push(i);
    pair = num / i;
    if (pair != i) {
      pairCount++;
      disvisorPairs.push(pair);
    }
  }
}
for (var i = pairCount - 1; i >= 0; i--) {
  divisors.push(disvisorPairs[i]);
}
if (num != 1) divisors.push(num);
console.log(divisors);

• Is there anything else I can do to increase the performance of my code?
• Is there a data structure other than arrays that can possibly sort the the divisors in constant time?