La sum de todos los múltiplos de 3 o 5 por debajo de 1000 da una respuesta incorrecta en C

Problema del proyecto Euler:

Si enumeramos todos los números naturales por debajo de 10 que son múltiplos de 3 or 5 , obtenemos 3, 5, 6 and 9 . La sum de estos múltiplos es 23 .

Encuentra la sum de todos los múltiplos de 3 or 5 debajo de 1000 .

Mi código C:

 long int x; long int y; long int z = 0; long int a = 0; long int b = 0; for(x= 0; x < 1000; x += 3) a = a + x; for(y = 0; y < 1000; y += 5) b = b + y; z = a + b; printf("%lu", z); return 0; 

Pero estoy obteniendo 266333 como la salida que está mal. Comprobé la respuesta con Python y lo hice bien. Me gustaría saber qué estoy haciendo mal con el código C. La respuesta correcta es 233168

Mi código de Python:

 print(sum(x for x in range(1000) if x % 3 == 0 or x % 5 == 0)) 

Algunos números serán divisibles entre 3 y 5, no debes sumrlos dos veces. Un código como este dará el resultado correcto:

 long int x,total = 0; for(x = 0; x < 1000; ++x) { if(x % 3 == 0) total = total + x; else if(x % 5 == 0) total = total + x; } printf("%ld", total); 

en el código anterior, if else if asegúrese de que si un número es divisible por 3 o por 5. Y permita resumir sobre esta base.

Puede optimizarse aún más para:

 for(x= 0; x < 1000; ++x) { if(x%3 == 0 || x%5 == 0) total = total + x; } 

La solución anterior es O (n) para una mejor complejidad de tiempo O (1) podemos usar la progresión aritmética con un intervalo de 3 y 5.

introduzca la descripción de la imagen aquí

n = número total de múltiplos de un número dado (Num) en un rango dado (1 ... R). en este caso (1 ... 1000)

a1 = primer múltiplo. Aquí será 3 o 5.

an = último múltiplo. es decir, 3Xn

Por lo tanto, el siguiente código calculará la sum de las series con el intervalo 3/5 (Num) para un rango dado 1 ... lastOfRange (excluyendo lastOfRange).

 long SumOfSeries(long Num, long lastOfRange) { long multiplesCount = (lastOfRange-1) / Num; //(lastOfRange-1) to exlude the last number 1000 here long result = multiplesCount * (Num + (multiplesCount * Num)) / 2;//Num = a1, (multiplesCount * Num) = an. return result; } 

y esto se puede llamar como:

 long N = 1000; Sum = SumOfSeries(3, N) + SumOfSeries(5, N) - SumOfSeries(3*5, N); printf("%ld", total); 

La respuesta se puede calcular con aritmética simple sin ninguna iteración. Muchas de las preguntas del Proyecto Euler tienen la intención de hacerle pensar en formas inteligentes de encontrar soluciones sin solo usar el poder en bruto de las computadoras para revisar los cálculos.

Dados los enteros positivos N y F , el número de múltiplos positivos de F que son menores que N es piso (( N -1) / F ). (floor ( x ) es el mayor entero no mayor que x .) Por ejemplo, el número de múltiplos de 5 menos que 1000 es floor (999/5) = floor (199.8) = 199.

Sea n este número de múltiplos, piso (( N -1) / F ).

El primer múltiplo es F y el último múltiplo es nF. Por ejemplo, con 1000 y 5, el primer múltiplo es 5 y el último múltiplo es 199 • 5 = 995.

Los múltiplos están espaciados uniformemente, por lo que el promedio de todos ellos es igual al promedio de la primera y la última, por lo que es ( F + * n ** F *) / 2.

El total de los múltiplos es igual a su promedio multiplicado por el número de ellos, por lo que el total de los múltiplos de F menor que N es n • ( F + nF ) / 2.

Como hemos visto en otras respuestas y en comentarios, sumr la sum de los múltiplos de 3 y la sum de los múltiplos de 5 cuenta los múltiplos de 3 y 5 dos veces. Podemos corregir esto restando la sum de esos números. Los múltiplos de las sums de 3 y 5 son múltiplos de 15.

Por lo tanto, podemos calcular la sum solicitada utilizando aritmética simple sin ninguna iteración:

 #include  static long SumOfMultiples(long N, long F) { long NumberOfMultiples = (N-1) / F; long FirstMultiple = F; long LastMultiple = NumberOfMultiples * F; return NumberOfMultiples * (FirstMultiple + LastMultiple) / 2; } int main(void) { long N = 1000; long Sum = SumOfMultiples(N, 3) + SumOfMultiples(N, 5) - SumOfMultiples(N, 3*5); printf("%ld\n", Sum); } 

Al hacer otras preguntas sobre el Proyecto Euler, debe buscar ideas similares.

Lo que estás haciendo es un error de cálculo. Usted ve que hay algunos múltiplos comunes de 5 y 3 como 15,30,45 … así que ya que los está sumndo en ambas sums, está obteniendo un valor mayor.

Una ligera modificación al código hará el truco.

 for(x= 0; x < 1000; x += 3) { if(x%5) { a = a + x; } } for(y = 0; y < 1000; y += 5) b = b + y; z = a + b; printf("%lu", z); 

Traducción directa de su código python:

 #include  int main(int argc, char *argv[]) { int sum = 0; for (int x = 0; x < 1000; x++) { if (x % 5 == 0 || x % 3 == 0) sum += x; } printf("%d", sum); } 

Por el gusto de hacerlo, decidí darle al problema algunas restricciones adicionales.

  • El iterador de bucle no puede tomar valores que no sean múltiples
  • Los números deben sumrse a la sum en orden numérico.

 int sum_multiples(long int m1,long int m2,long int lim) { long int sum=0; for(long int i=m1;i((i+m2)/m2)*m2?((i+m2)/m2)*m2:((i+m1)/m1)*m1) sum+=i; return sum; } int main(int argc, char *argv[]) { printf("Total: %ld \n",sum_multiples(3,5,1000)); return 0; }