c# - 如何找出一些给定素数最接近 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)
    }