• Domingo 15 de Diciembre de 2024, 09:21

Autor Tema:  Project Euler (problema 10)  (Leído 1969 veces)

SkullFlower

  • Miembro activo
  • **
  • Mensajes: 25
    • Ver Perfil
Project Euler (problema 10)
« en: Martes 20 de Julio de 2010, 04:29 »
0
Bueno, estoy intentando resolver algunos problemas de la pagina projecteuler y ya llegue al 10 pero por alguna razón no me sale.

el problema dice así:

Citar
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

el código que tengo hasta ahorita es este:

Código: C
  1. #include<stdio.h>
  2. #include<math.h>
  3. int main(){
  4.     int lim = 2000000;
  5.     int i, j;
  6.     int sieve[lim];
  7.     int sum;
  8.     sum = 0;
  9.     for(i=1;i<=lim;i++){
  10.         sieve[i]=1;
  11.         if(i<2){
  12.             sieve[i]=0;
  13.         }
  14.     }
  15.     for(i=4;i<=lim;i+=2){
  16.         sieve[i]=0;
  17.     }
  18.     for(i=3;i<=sqrt(lim);i+=2){
  19.         if(sieve[i]){
  20.             for(j=i*2;j<=lim;j+=i){
  21.                 sieve[j]=0;
  22.             }
  23.         }
  24.     }
  25.     for(i=1;i<=lim;i++){
  26.         if(sieve[i]){
  27.             sum+=i;
  28.         }
  29.     }
  30.     printf("%dn", sum);
  31.     return 0;
  32. }
  33.  

el resultado que me da es: 1179908154

pero yo se que ese no es el resultado correcto, el resultado correcto es: 142913828922

asi que no se que este haciendo mal  :wacko:

czealt

  • Miembro activo
  • **
  • Mensajes: 28
    • Ver Perfil
Re: Project Euler (problema 10)
« Respuesta #1 en: Martes 20 de Julio de 2010, 23:54 »
0
Citar
...el resultado que me da es: 1179908154

pero yo se que ese no es el resultado correcto, el resultado correcto es: 142913828922
Te da ese resultado porque usas una variable de tipo int para contener la suma de los números primos. Las variables de tipo int solo pueden contener valores en el rango
 
 -2147483648 <= int <= 2147483647 (en compiladores de 32 bits)

La suma total de los números (142913828922) queda fuera de ese rango por lo que no puede ser representada con variables int..

Probé usando una variable de tipo double y dio el resultado correcto.

Ah una cosa  más, los indices de los arreglos en C y C++ comienzan en 0 no en 1 asi que también se tuvo que corregir eso

Código: C++
  1.  
  2. ...
  3. int sieve[lim+1];
  4. double sum;
  5. ...
  6. for(i=1;i<=lim;i++){
  7.   if(sieve[i])
  8.     sum+=i;
  9. }
  10.  
  11. printf("%.0fn", sum);
  12.  
  13.  
Saludos.

SkullFlower

  • Miembro activo
  • **
  • Mensajes: 25
    • Ver Perfil
Re: Project Euler (problema 10)
« Respuesta #2 en: Miércoles 21 de Julio de 2010, 02:21 »
0
bueno ya lo corregí el problema era ese que dices que estaba usando int, así que use un long long.

y con respecto a lo que mencionas sobre el arreglo, no me da ningún problema así que lo deje como lo tenia.

bueno aquí dejo el código corregido para que lo use el que quiera:

Código: C
  1. #include<stdio.h>
  2. #include<math.h>
  3. int main(){
  4.     int lim = 2000000;
  5.     int i, j;
  6.     int sieve[lim];
  7.     long long sum;
  8.     sum = 0;
  9.     for(i=1;i<=lim;i++){
  10.         sieve[i]=1;
  11.         if(i<2){
  12.             sieve[i]=0;
  13.         }
  14.     }
  15.     for(i=4;i<=lim;i+=2){
  16.         sieve[i]=0;
  17.     }
  18.     for(i=3;i<=sqrt(lim);i+=2){
  19.         if(sieve[i]){
  20.             for(j=i*2;j<=lim;j+=i){
  21.                 sieve[j]=0;
  22.             }
  23.         }
  24.     }
  25.     for(i=1;i<=lim;i++){
  26.         if(sieve[i]){
  27.             sum+=i;
  28.         }
  29.     }
  30.     printf("%lldn", sum);
  31.     return 0;
  32. }
  33.  

gracias por la ayuda czealt.  :beer:

czealt

  • Miembro activo
  • **
  • Mensajes: 28
    • Ver Perfil
Re: Project Euler (problema 10)
« Respuesta #3 en: Miércoles 21 de Julio de 2010, 18:17 »
0
de nada man  :good: