如何找出一些给定素数的最近可能组合到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方法接受素数数组,例如2,3,5,2851,13.

在上面的例子中,它应该分配:

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

如何实现逻辑？

Answer 1

然后遍历从 10,000 到 2 的每个数字。对于每个数字，测试该数字的质因数分解是否是给定列表的子集。如果是的话，那么我们就找到了答案。

Partition1是该数的质因数。Partition2简直就是primeNumbers - Partition1。

这是伪代码：

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

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