如何找出一些给定素数最接近10000的可能组合

本文关键字：10000 最接近 组合 何找出 | 更新日期: 2023-09-27 18:13:27

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;

如何实现逻辑?

如何找出一些给定素数最接近10000的可能组合

然后遍历从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)
    }

我的解决方案如下

private void SetPartitions(List<int> primeNumbers, int bound)
{
    int[] mods = new int[primeNumbers.Count];
    for(int i = 0; i < primeNumbers.Count; i++)
        mods[i] = bound % primeNumbers[i];
    int count = bound;
    do
    {
        int temp = count;
        for(int j = 0; j < mods.Length; j++)
            if(mods[j] == 0) 
                temp /= primeNumbers[j];
        if(temp == 1)
        {
            this.Partition1 = count;
            for(int k = 0; k < mods.Length; k++)
                if(mods[k] != 0)
                    temp *= primeNumbers[k];
            this.Partition2 = temp;
            return;
        }
        else
        {
            for(int k = 0; k < mods.Length; k++)
                mods[k] = (mods[k] == 0) ? primeNumbers[k] - 1 : mods[k] - 1;
            count--;
        }
    }while(true);
}

我想这是作业。经检验，答案是2 * 4999(9998)。

暴力破解技术是(应该是)显而易见的。取一个所有质数x的列表，使得0 <= x <= 5000(由于您在这里寻找因子，因此您将使用数字相乘…因为最小的素数是2，所以你不需要担心大于5000的数)。对于列表中的每个项，再次遍历列表，检查列表中的每个y。将它们相乘，记录乘积与10000之间的增量。保留最小的那个

另一种方法是从10000开始，计算它的质因数(如果有的话)。

http://mathworld.wolfram.com/PrimeFactorization.html

http://mathworld.wolfram.com/PrimeFactorizationAlgorithms.html

例如:

int i = 10000 ;
int[] primeFactors = null ;
while ( i > 0 && ( primeFactors == null || primeFactors.Length == 0 ) )
{
  primeFactors = ComputePrimeFactorsOf( i ) ;
}
// if primeFactors is contains data, there's your solution

听起来像是对背包问题的重新表述。而你的是乘法，计算质数和目标数的对数，将其转化为加法问题。

但即使一般的背包问题很难，你的特定子集的问题可能有一个快速的解决方案。

自2^14 = 16384以来，您最多可以有13个素数因子，其中最多可以有5个素数因子(因为2*3*5*7*11*13 = 30030 > 10000)。最简单的解决方案是遍历所有组合。如果你想让其中一种产物最接近10000，那么你要遍历所有的东西。如果您只想要一个两个分区的乘积都小于10,000的分区，那么您可以在找到解决方案后立即停止。即使没有任何优化，在今天的机器上，这应该只需要几分之一秒。

 internal static void GetPartitionsClosestTo9999(List<long> primeFactors, out long partition1, out long partition2)
        {
            for (var index = 9999; index >= 2; index--)
            {
                var primeFactorsForCurrentIndex = GetPrimeFactors(index);
                var isSubset = IsSubSet(primeFactorsForCurrentIndex, primeFactors); //!primeFactorsForCurrentIndex.Except(primeFactors).Any();
                if (isSubset)
                {
                    partition1 = index;
                    foreach (var primeFactorForCurrentIndex in primeFactorsForCurrentIndex)
                    {
                        primeFactors.Remove(primeFactorForCurrentIndex);
                    }
                    partition2 = GetProduct(primeFactors);
                    return;
                }
            }
            throw new ApplicationException("No subset found.");
        }
        static bool IsSubSet<T>(ICollection<T> set, IEnumerable<T> toCheck)
        {
            return set.Count == (toCheck.Intersect(set)).Count();
        }
相关文章：