Get X amount of integers that can all be multiplied together to get close to Y

Question

It's hard to explain in just the title, but basically I have created a system that inputs some number N and outputs two numbers (excluding 1 and N) that can be multiplied together to be as close to N as possible (going over instead of under).

Here's a few examples:

• 25 → 5 & 5.
• 40 → 5 & 8.
• 53 → 6 & 9.
• 13 → 2 & 7.

I have a method Factor that returns a list of all factors of X sans 1 and X. This code also doesn't need to work with big numbers, so I test for primality by checking if it's in a list of prime numbers.

The code that does it is here:

if (primes.Contains(N))
        N++;
List<int> facts = Factor(N);
double root = Math.Sqrt(N);
int cl1;
int cl2;
if (root == (int)root)
{
    cl1 = (int)root;
    cl2 = (int)root;
}
else if (N == 2)
{
    cl1 = 1;
    cl2 = 2;
}
else
{
    cl1 = facts.Aggregate((x, y) => Math.Abs(x - root) < Math.Abs(y - root) ? x : y);
    facts.Remove(cl1);
    cl2 = facts.Aggregate((x, y) => Math.Abs(x - root) < Math.Abs(y - root) ? x : y);
}

What would be a good way to generalize this so it could give three outputs, or four or five or nine? (Obviously I would swap out cl1 and cl2 with an array, but I mean code-wise)

Answer 1

Getting all the factors of N is a pretty expensive operation. It will actually be faster to do it like this (pseudocode):

For p = floor(sqrt(N)); p>1; --p:    
  q = ceil(N/p);
  error = p*q-N; //always positive
  record=make_tuple(p,q,error);
  //... remember the records with the smallest error

The best way to maintain the list of records depends on how many you want. Call that number M.

If it's just a few, then you can just put them in a list and whenever the list size gets to 2M, sort it by error and truncate to size M.

If it's a lot, then put them in a priority queue with max error first, and whenever the size is >M, remove the one with the highest error. At the end you can pull them out in reverse order and fill your output array backwards