Probemos una analogía lejos de las matemáticas, como una forma de entender lo que está sucediendo.
Acabo de revisar las recetas en la caja de la mezcla para hornear que uso para panqueques y waffles.
Los panqueques necesitan 2 tazas de la mezcla, 2 huevos y 1 taza de leche.
- ¿Cuánto estrés se le da a los algoritmos y las estructuras de datos en el curso de pregrado en CMI? ¿Se enseña programación competitiva allí?
- ¿Es necesario codificar todos los datos en estructuras como pilas en C ++, o es un conocimiento práctico suficiente para aclarar entrevistas?
- ¿Siempre es bueno tener una solución recursiva que una solución iterativa?
- ¿Qué series matemáticas debo saber para calcular la complejidad de cualquier algoritmo o pseudocódigo?
- ¿Cuántas conjeturas necesitarías para determinar el número entre 1 y 100 en el peor de los casos usando una búsqueda lineal?
Los waffles necesitan 1,5 tazas de la mezcla, 1 taza de leche, 1 huevo y 3 cucharadas de aceite vegetal.
¿Qué necesito disponer en el mostrador para preparar panqueques o waffles, sin que me falte un artículo de donde está almacenado?
Usted resuelve esta pregunta ordenando ambos conjuntos de ingredientes, reuniendo todo lo necesario para uno, digamos los panqueques. Luego, revise la lista de waffles para agregar los ingredientes que el waffle necesita, pero no son necesarios para los panqueques.
Cuando usa la factorización prima, está encontrando las dos listas de números primos con los que puede hacer cada número (a través de la multiplicación). Luego comienza con una de las listas y agrega solo los números primos encontrados en la segunda lista que no estaban en la primera.
Entonces, para 12, su lista era 2, 2, 3
La lista para 14 es 2, 7
Los dos 2 de la lista de factores primos para hacer 12 son más 2 de los que necesita hacer 14. Los waffles solo necesitaban 1 huevo, y los ingredientes del panqueque necesitaban 2. Los suministros para panqueques satisfacían la cantidad necesaria para los waffles.
Pero la lista para 14 también necesita un 7, que ni siquiera figura entre los factores de 12. Es como el aceite vegetal necesario para los waffles.
El método da como resultado el mínimo común (el más pequeño) múltiplo porque la combinación cuidadosa de los números primos asegura que solo se recopilan los ingredientes más simples que se necesitan, a partir de los cuales se puede hacer cualquier número.