CODEWITHSUNDEEP
c#algorithmmath
The Light
The Light

Reputation: 27021

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

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?

Upvotes: 8

Views: 689

Answers (6)

The Light
The Light

Reputation: 27021

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

Upvotes: 0

Alex Kovanev
Alex Kovanev

Reputation: 1888

My solution is below 

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

Upvotes: 1

Jeffrey Sax
Jeffrey Sax

Reputation: 10323

Since 2^14 = 16384, you can have at most 13 prime factors, of which at most 5 can be distinct (because 2*3*5*7*11*13 = 30030 > 10000). The simplest solution is to iterate over all combinations. If you want one of the products to be the closest to 10,000, then you go through everything. If you only want one in which both partitions' product is less than 10,000, you can stop as soon as you have a solution. Even with no optimization at all, this should only take a fraction of a second on today's machines.

Upvotes: 0

CodesInChaos
CodesInChaos

Reputation: 108830

Sounds like a reformulation of knapsack problem. While yours is multiplicative calculating the logarithm of the primes and the target number transforms it into an additive problem.

But even if the general Knapsack problem is hard, your particular subset of problems might have a fast solution.

Upvotes: 0

tskuzzy
tskuzzy

Reputation: 36476

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

Upvotes: 1

Nicholas Carey
Nicholas Carey

Reputation: 74307

I assume this is homework. The answer is 2 * 4999 (9998), by inspection.

The brute force technique is (should be) obvious. Take a list of all primes x such that 0 <= x <= 5000 (since you're looking for factors here, you'll be multiplying numbers...and since the smallest prime is 2, you don't need to worry about anything larger than 5000). for each item xin the list, iterate over the list again examining each y in the list. Multiply them together and record the delta between the product and 10000. Keep the smallest one.

Another way of doing it would be to start with 10000 and compute its prime factors (if any).

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

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

For instance:

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

Upvotes: 0

Related Questions