How to find out the closest possible combination of some given prime numbers to 10000?

Question

public int Partition1 {get;set;}
public int Partition1 {get;set;}

private void SetPartitions(List<int> primeNumbers)
{       
    this.Partition1 = // get the product of the prime numbers closest to 10000
    this.Partition2 = // get the product of the remaining prime numbers            
}

SetPartitions method accepts an array of prime numbers such as 2, 3, 5, 2851, 13.

In the above example, it should assign:

this.Partition1 = 2851 * 3; // which is 8553 and closest possible to 10000
this.Partition2 = 2 * 5 * 13;

How to implement the logic?

Answer 1

Then go through each number from 10,000 to 2. For each of these, test to see if the prime factorization of the number is a subset of the given list. If it is, then we have found the answer.

Partition1 is the prime factors of the number. Partition2 is simply primeNumbers - Partition1.

Here's the psuedocode:

for n=10000 to 2
    factors = prime_factorization(n)

    if( factors is subset primeNumbers ) {
        partition1 = factors
        partition2 = primeNumbers - factors
        return (partition1,partition2)
    }