Vtgyjfy

I want to be able (using a computer), to multiply $26$ integer numbers (from $1$ to $52$) but prevent the product from growing very large because it seems to maybe be causing some problems in the computer language I am using. So I want to know if there is a good way to limit the product so that all of the factors can still be divided into the resulting product without any remainder. Shrinking the example down to only $4$ numbers for simplicity (but remember the real world scenario will have $26$ numbers to multiply together), suppose we had $2, 3, 5$, and $50$. Simply multiplying them together would give $2*3*5*50=1500$. However, we don't need $1500$ because $150$ will suffice. So is there a way (ideally "on the fly") to get to $150$ as I see the numbers in order ($2,3,5,50$)? I would get $2*3=6$ then I would get $6*5=30$ but then how to get from $30$ to $150$? Maybe just keep a list of all factors (and quantities of them) seen so far so when I get to $2*3*5=30$, then I see $50$, since $50$ is $2*5*5$ and I have already seen $2*5$ once, just add in the 2nd $5$ to get $30*5=150$?

Also in reality, the partial products will be very large, not small like in this simplified example.

I will add an example shortly of $26$ numbers that need to be multiplied such that the product is minimal (or near minimal such as $2$x minimal).

The algorithm I am looking for can be multiple pass, meaning an initial scan of the numbers can be made and remove factors such as $13$ when there is also a factor of $26$ or $39$ already. The 2nd pass could me more along the lines of a LCM algorithm but since I am using an interpreted language, I would like it to be fast running.

A real example of $26$ numbers needing to be multiplied (but with LCM) is:

$3,4,5,7,9,10,11,12,14,15,18,20,21,22,24,26,28,30,33,35,36,39,40,42,45,52$

I wonder what the LCM of all these are. Notice terms like $24$ and $36$ would just drop out since we already have $12$. Also $22$ and $33$ would drop out since we have $11$ already. I am not sure but I think the LCM would be $3*4*5*7*11*3*13*14 = 2,522,520$

Old question, but fun puzzle.

For each prime, it will be included in your results with a multiplicity equal to it's max for any given number in the list.
For example, if your list contains no multiple of 7's except 49, then 7 will have a power of 2.

This code counts primes in such a way. It's C# and not a math language, but I'm sure you can translate.

using System;

using System.Collections;

using System.Collections.Generic;

using System.Linq;



namespace ConsoleApp5

{

    public class Program

    {

        private const int Max = 1000;

        private static readonly int Primes = PrimesLessThan(Max);



        private static int PrimesLessThan(int max)

        {

            var composite = new BitArray(max);

            var maxSqrRt = (int) Math.Sqrt(max);

            for (var i = 2; i < maxSqrRt; i++)

            {

                if (composite[i])

                {

                    continue;

                }



                for (var j = i * i; j < max; j += i)

                {

                    composite[j] = true;

                }

            }



            var values = new List<int> {2};

            for (var i = 3; i < max; i += 2)

            {

                if (!composite[i])

                {

                    values.Add(i);

                }

            }



            return values.ToArray();

        }



        public static void Main()

        {

            Console.WriteLine(string.Join(", ", Primes.Select(x => x.ToString())));

            Console.Write(Lcm(3, 4, 5, 7, 9, 10, 11, 12, 14, 15, 18, 20, 21, 22, 24, 26, 28, 30, 33, 35, 36, 39, 40, 42, 45, 52));

            Console.ReadKey();

        }



        private static int Lcm(params int args)

        {

            var primesCount = Primes.Length;

            var slots = new int[primesCount];

            foreach (var i in args)

            {

                var number = i;

                for (var j = 0; j < primesCount && number > 1; j++)

                {

                    var prime = Primes[j];

                    var count = 0;

                    while (number % prime == 0)

                    {

                        number /= prime;

                        count++;

                    }



                    if (count > slots[j])

                    {

                        slots[j] = count;

                    }

                }

            }



            var result = 1;

            for (var i = 0; i < primesCount; i++)

            {

                result *= (int)Math.Pow(Primes[i], slots[i]);

            }



            return result;

        }

    }

}

The result is 360360, which you've gotten wrong by including 14 in your multiplication, you need to remove it and add 1 to the power for 2. For ease of use you'd want this: 2^3 * 3^2 * 5 * 7 * 11 * 13