proyecto euler ejercicio 5 enfoque

Pregunta: 2520 es el número más pequeño que se puede dividir por cada uno de los números del 1 al 10 sin ningún rest.

¿Cuál es el número positivo más pequeño que es divisible por todos los números del 1 al 20?

Entonces, estaba tratando de hacer el ejercicio 5 en el proyecto euler y salí con este código:

#include  #define TRUE 1 #define FALSE 0 int main () { int n, fnd = FALSE, count, i; for (i = 1; fnd == FALSE; i++) { count = 0; for (n = 1; n <= 20; n++) { count += i % n; } printf ("testing %d, count was: %d\n", i, count); if (count == 0) { fnd = TRUE; printf ("%d\n", i); } } return 0; } 

Creo que mi apporach es correcto, seguramente encontrará el número que es divisible entre 1 y 20. Pero se ha estado computando durante 5 minutos, y aún no hay resultados. ¿Mi enfoque es correcto? Si es así, entonces ¿hay otra manera de hacerlo? No puedo pensar en otra forma de resolver esto, los consejos serían muy apreciados. Gracias de antemano.

EDIT: Entonces, basado en el consejo que me dieron, chicos, lo descubrí, ¡muchas gracias! Entonces, sigue siendo fuerza bruta, pero en lugar de sumr 1 al último número, ahora sum 2520, que es el MCM de 1 a 10. Y, por lo tanto, calcula si la sum de los rests de los múltiplos de 2520 se divide de 11 a 20 era 0. Dado que 2520 ya es divisible entre 1 y 10, solo necesitaba dividir entre 11 y 20.

 #include  #define TRUE 1 #define FALSE 0 int main () { int n, fnd = FALSE, count, i; for (i = 2520; fnd == FALSE; i = i + 2520) { count = 0; for (n = 11; n <= 20; n++) { count += i % n; } printf ("testing %d, count was: %d\n", i, count); if (count == 0 && i != 0) { fnd = TRUE; printf ("%d\n", i); } } return 0; } 

Muchas gracias, no lo resolvería sin su ayuda:) PD: ahora se calcula en menos de 10 segundos.

Su enfoque está tomando demasiado tiempo porque es una solución de fuerza bruta. Necesitas ser un poco inteligente.

Mi sugerencia para usted es la siguiente: ¿qué significa que un número sea divisible de manera equitativa por otro número? ¿O cada número debajo de un cierto número? ¿Hay puntos en común en los factores primos de los números? La página de Wikipedia sobre divisibilidad debería ser un buen punto de partida.

Pista: deberías buscar “mínimo común múltiplo”.


Siguiente pista:

  1. La respuesta es el mínimo común múltiplo (MCM) de los números 1, 2, 3, …, 20.
  2. El LCM de n números se puede encontrar secuencialmente: si LCM (1, 2) = x , que LCM (1, 2, 3) = LCM ( x , 3); si LCM (1, 2, 3) = y , que LCM (1, 2, 3, 4) = LCM ( y , 4), etc. Así que es suficiente saber cómo encontrar LCM de 2 números.
  3. Para encontrar MCM de 2 números podemos usar la siguiente fórmula: LCM ( p , q ) = pq / GCD ( p , q ), donde GCD es el mayor divisor común
  4. Para encontrar GCD, existe un conocido algoritmo de Euclides (quizás el primer algoritmo no trivial en la Tierra).

Creo que debería comenzar calculando los factores primos de cada número del 2 al 20. Dado que el número deseado debe ser divisible por cada número del 1 al 20, también debe ser divisible por cada factor primo de esos números.

Además, es importante hacer un seguimiento de las multiplicidades de los factores primos. Por ejemplo, 4 = 2 * 2, por lo tanto, el número deseado debe ser divisible por 2 * 2.

Algo que rápidamente cociné con Python 3:

 primary_list = [] for i in range(2, 4097): j = i k = 2 delta_list = primary_list[0:] alpha_list = [] while j > 1: if j % k == 0: j /= k alpha_list.append(k) k = 2 else: k += 1 for i in alpha_list: try: delta_list.remove(i) except: primary_list.append(i) final_number = 1 for i in primary_list: final_number *= i print(final_number) 

Esto se calcula en meros segundos bajo una máquina lenta . Python es muy bueno con los números abstractos. La mejor herramienta para el trabajo.

El algoritmo es relativamente simple. Tenemos una lista básica primary_list donde almacenamos los múltiplos de los números. Luego viene el bucle donde estimamos el rango de números que queremos calcular. Utilizamos una variable temporal j como un número que se puede dividir, cortar y conquistar fácilmente. Usamos k como el divisor, comenzando como 2 . La lista delta es la copia de trabajo principal de la lista principal, donde separamos número tras número hasta que solo queda la ” lógica ” requerida. Luego agregamos esos números a nuestra lista principal.

1: 1
2: 2 1
3: 3 1
4: 2 2 1
5: 5 1
6: 2 3 1
7: 7 1
8: 2 2 2 1
9: 3 3 1
10: 2 5 1

El número final se encuentra multiplicando los números que tenemos en la lista_primaria .
1 * 2 * 3 * 2 * 5 * 7 * 2 * 3 = 2520

Como se dijo, Python es realmente bueno con los números. Es la mejor herramienta para el trabajo. Por eso debería usarlo en lugar de C, Erlang, Go, D o cualquier otro lenguaje dynamic / estático para los ejercicios de Euler.

Lo resolví usando C. ¡Abajo está el algoritmo!

 #include  #include  int main() { int i; int count; for(i=21;i>0;i++) { count = 0; for( int j=2;j<21;j++) { if (i%j!=0) break; count++; } if (count==19) break; } printf("%d\n",i); return 0; } 

Sólo algunos pensamientos sobre los comentarios anteriores,

@ pg190 usted dice “realmente solo necesita ser divisible por los números primos entre 1 y 20, es decir, 2, 3, 5, 7, 11, 13, 17, 19”. tomar 9699690, no se divide por todos los valores de 1-20.

Así que esta podría ser una buena solución,

Dado el conjunto de números [1-20]

El mínimo común múltiplo se puede calcular de la siguiente manera.

Ex. Para los números 2,6,9.

Expresalos en multiplicaciones primas 2 2

6 2 3

9 3 3

LCM = múltiplo de la potencia más alta de cada número primo. = 2 * 3 ^ 2 = 18

Esto se puede hacer para resolver el problema en cuestión al express cada número como multiplicación principal y luego hacer estos cálculos matemáticos.

 $num=20; for($j=19;$j>1;$j--) { $num= lcm($j,$num); } echo $num; function lcm($num1, $num2) { $lcm = ($num1*$num2)/(gcd($num1,$num2)); return $lcm; } function gcd($n1,$n2) { $gcd=1; $min=$n1; if($n1>$n2) { $min=$n2; } for($i=$min;$i>1;$i--) { if($n1%$i==0 && $n2%$i==0) { $gcd*=$i; $n1/=$i; $n2/=$i; } } return $gcd; } 

resuelto en php