Proyecto Euler 5

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?

Mi solución:

#include int gcd(int m, int n); int lcm(int a, int b); int main() { int x=1, i; for(i=1; in) m=mn; else n=nm; } return m; } int lcm(int a, int b) { return ((a*b)/gcd(a, b)); } 

Por favor, dime dónde estoy equivocado? Muestra solo pantalla en blanco al correr.

Si solo hay una lección que aprendes de este ejercicio, hazlo de esta manera: el orden en el que haces tus multiplicaciones y divisiones es importante .

Incluso si no importa en matemáticas, a menudo importa en su progtwig. Por ejemplo, en matemáticas no hay diferencia entre (a*b)/gcd(a, b) y a/gcd(a, b)*b ; En su progtwig, haría la diferencia entre pasar y fallar.

(PS, por supuesto, también necesita corregir el error en su lógica: no debe multiplicar x por mcm).

EDITAR

Para entender por qué el orden hace la diferencia aquí, considera calcular el lcm de 232792560 y 20 . 232792560 es divisible por 20 , entonces es el lcm . Sin embargo, cuando calcula 232792560*20 , obtiene un desbordamiento; luego divides por 20 , pero no obtienes 232792560 vuelta.

Como el divisor es gcd(a,b) , puedes dividirlo de a antes de multiplicar por b sin truncar el resultado por división entera. Este pequeño truco que los progtwigdores experimentados usan sin pensar puede ahorrarle horas de depuración.

La mayoría de los problemas en el Proyecto Euler se pueden resolver de tres maneras:

  • con fuerza bruta
  • con un algoritmo que resuelve un problema más general (como lo hace usted)
  • Con una solución inteligente que requiere lápiz y papel a lo sumo.

Si está interesado en una buena solución en lugar de arreglar su código, intente concentrarse en el último enfoque:

El truco consiste en encontrar el conjunto múltiple más pequeño de números primos, de modo que cualquier número entre 1 y 20 pueda expressse como un producto de algunos de estos números primos.

 1 = 1 11 = 11 2 = 2 12 = 2*2*3 3 = 3 13 = 13 4 = 2*2 14 = 2*7 5 = 5 15 = 3*5 6 = 2*3 16 = 2*2*2*2 7 = 7 17 = 17 8 = 2*2*2 18 = 2*3*3 9 = 3*3 19 = 19 10 = 2*5 20 = 2*2*5 

Al “ORing” los factores primos para los números entre 1 y 10, obtenemos 1*2*2*2*3*3*5*7 , que es 2520, tal como se esperaba.

Ahora, si pasamos de 1 a 20, obtenemos 1*2*2*2*2*3*3*5*7*11*13*17*19 , que de hecho es aceptado por el Proyecto Euler.

Un printf() le mostraría que su código se está metiendo en un bucle infinito. He añadido un printf() en el gcd() en el bucle while.

  n=nm; printf("m=%dn=%d\n", m, n); } return m; 

while(m!=n) nunca es cierto para n=14 . Finalmente, el n desborda porque x va a un número más alto que no puede acomodarse por tipo int .

El error es x*=lcm(x, i+1); y aquí está la solución completa,

 long gcd(long m, long n); long lcm(long a, long b); int main() { long x=1; for(int i=2; i<=20; i++) { x=lcm(x,i); } cout << "The answer is: " << x << endl; return 0; } long gcd(long a, long b) { return (b==0)?a:gcd(b,a%b); } long lcm(long a, long b) { return ((a*b)/gcd(a, b)); } 

El n-1 debe ser n; y x = lcm (…) no x * = lcm (…). Pero no veo muy bien (lejos de la terminal) dónde se atasca el bucle.

La respuesta para 20 es: 232792560.

Estas son todas las respuestas para todos los números cuya respuesta se ajusta a un entero largo:

1: 1
2: 2
3: 6
4: 12
5: 60
6: 60
7: 420
8: 840
9: 2520
10: 2520 <=== ejemplo en la pregunta de Euler P5 para la división de 1 a 10 sin el resto
11: 27720
12: 27720
13: 360360
14: 360360
15: 360360
16: 720720
17: 12252240
18: 12252240
19: 232792560
20: 232792560 <== respuesta para Euler Prog 5 (1 a 20 sin el resto
21: 232792560
22: 232792560
23: 5354228880
24: 5354228880
25: 26771144400
26: 26771144400
27: 80313433200
28: 80313433200
29: 2329089562800
30: 2329089562800
31: 72201776446800
32: 144403552893600
33: 144403552893600
34: 144403552893600
35: 144403552893600
36: 144403552893600
37: 5342931457063200
38: 5342931457063200
39: 5342931457063200
40: 5342931457063200
41: 219060189739591200
42: 219060189739591200