Как найти максимально возможную комбинацию некоторых заданных простых чисел до 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

Мое решение ниже

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);
}

Answer 2

Затем просмотрите каждое число от 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)
    }

Answer 3

 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();
        }

Answer 4

Начиная с 2^14 = 16384, вы можете иметь не более 13 основных факторов, из которых не более 5 могут быть различимы (потому что 2*3*5*7*11*13 = 30030 > 10000).Самое простое решение - перебрать все комбинации.Если вы хотите, чтобы один из продуктов был ближе всего к 10000, то вы должны пройти через все.Если вам нужен только тот, в котором продукт обоих разделов меньше 10 000, вы можете остановиться, как только у вас будет решение.Даже без какой-либо оптимизации на современных машинах это займет всего лишь долю секунды.

Answer 5

Звучит как переформулировка проблемы с рюкзаком . В то время как ваш умножается на умножение, вычисляется логарифм простых чисел, а целевое число превращает его в аддитивную задачу.

Но даже если общая проблема с рюкзаком сложная , у вашей конкретной группы проблем может быть быстрое решение.

Answer 6

Я предполагаю, что это домашнее задание. Ответ 2 * 4999 (9998), осмотр.

Техника грубой силы очевидна (должна быть). Возьмите список всех простых чисел x, таких, что 0 <= x <= 5000 (так как вы ищете здесь факторы, вы будете умножать числа ... и так как наименьшее простое число равно 2, вам не нужно беспокоиться ни о чем больше 5000). для каждого элемента в списке, повторите итерацию по списку снова, изучая каждый y в списке. Умножьте их вместе и запишите дельту между продуктом и 10000. Оставьте наименьшее значение. </p>

Другой способ сделать это - начать с 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