¿Cómo realizo "Millones de cálculos?"

Question

Mi código está pegado a continuación. Cuando ejecuto este programa, sigue calculando.Estoy usando el viejo compilador de Turbo C++. ¿Cuánto tiempo debería tardar un programa en ejecutarse? Esperé unos 5 minutos pero no había ningún salida.

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

Find the sum of all the primes below two million. 
*/ 
#include<stdio.h> 
#include<conio.h> 
#define TWO_MILLION 2*1000*1000 
int IsPrime(long unsigned int num); 
int main() 
{ 
    long unsigned int i,sum=0; 
    clrscr(); 
    for(i=2;i<TWO_MILLION;i++) 
    { 
     if(IsPrime(i)) 
     sum+=i; 
    } 
    gotoxy(25,25); 
    printf("%ld",sum); 
    getch(); 
    return 0; 
} 
int IsPrime(long unsigned int num) 
{ 
    int flag=1; 
    long unsigned int i; 
    for(i=2;i<num;i++) 
    { 
     if(num%i==0) 
     { 
      flag=0; 
      break; 
     } 
    } 
    return flag; 
} 

Answer 1

No está haciendo millones de cálculos, está haciendo billones de ellos.

IsPrime se ejecutará en el tiempo O (n), es decir, realizará 2 millones de instrucciones solo para determinar ese número único. Hacer ese tipo de cosas dos millones de tiempo tomará demasiado tiempo.

Para hacer esto, realmente quiere usar algo como: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes, que puede determinar mucho más eficientemente todos los números primos en un rango particular.

Answer 2

¿Cuánto tiempo debe tener un programa de este tipo para ejecutar?

Eso depende completamente de su plataforma. Sospecho que ya estás realizando ~ (dos millones)^2 operaciones (~ cuatro billones) de cálculos, un tiempo horrible.

Hay formas mucho mejores de realizar lo que está haciendo; por ejemplo, para comprobar el estado primordial solo necesita comprobar la raíz cuadrada del número, no hasta el número mismo. Sin mencionar que probablemente haya una solución de programación dinámica que puede hacerlo mucho más rápido que eso.

Answer 3

Esto podría tomar un muy largo tiempo para ejecutar.

Añadir esto para ver su progreso (aunque llevará más tiempo):

for(i=2;i<num;i++) 
    { 
     if(num%i==0) 
     { 
      flag=0; 
      printf("%d,", num); /* <== show the prime */ 
      break; 
     } 
    } 

Editar

Como otros están señalando, esta es la manera más lenta para contar los números primos. Tal vez el propósito de su tarea es lograr que busque (e implemente) los más rápidos.

Answer 4

Como han dicho otros, llevará mucho tiempo. Un enfoque alternativo e interesante es el Tamiz de Eratóstenes. Usted puede leer sobre él en:

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Básicamente inicializar una matriz con los números 2 ... 2 millones. El número más bajo aún no procesado es primo. Luego, elimina todos los múltiplos de este número de la matriz y continúa. Funcionará mucho más rápido que lo que tienes.

Answer 5

fuera de compás respuesta

gotoxy(25,25);

Hace usted funciona el programa en modo texto? Si la pantalla de texto es solo 80 x 25, y si la línea 25 está ocluida por algunas otras cosas, entonces es probable que no vea ningún cambio en la pantalla de texto.

Answer 6

Su programa da como resultado un desbordamiento de entero, puede usar un largo tiempo para arreglarlo.

Además, su algoritmo para comprobar si un número es primo no es muy bueno. Otra forma igual de fácil es probar los números 2 a la raíz cuadrada del número. Solo tiene que verificar la raíz cuadrada del número para determinar si es primo.

Answer 7

Un simple cambio le mostraría qué tan rápido se está ejecutando su programa y cuánto trabajo tiene que hacer. Es fácil imprimir su estado alrededor de cada 100 iteraciones. (O usted puede configurarlo a 1000 o 10000 iteraciones.)

---

Reconocer que usted podría DOBLE la velocidad de su bucle en IsPrime.
Después de marcar 2, solo necesita verificar los números impares, y podría avanzar con i+=2 en lugar de i++.

Si le preocupa la velocidad, ¿por qué pasa tanto tiempo revisando números pares? (tenga en cuenta que una vez que empiece a hacer sólo números impares, también es necesario cambiar la prueba de salida a ser un número impar)

Se pueden ingresar DOBLE la velocidad del bucle en main así por evitando también los números pares ahí. (otra vez, tiene que usar el caso especial 2, luego use i + = 2, comenzando en 3 para obtener 3, 5, 7, 9 ...)

Al hacer que el ciclo en IsPrime corra dos veces más rápido, y haciendo que el ciclo en main funcione dos veces más rápido, esto debería hacer que su programa sea 4X más rápido. (Si hubiera llevado una hora antes, ahora que va a ser de 15 minutos.)

---

La otra gran mejora de velocidad se podría hacer solamente está ejecutando el bucle para sqrt(num), en lugar de num

Como odio traer funciones de punto flotante, como sqrt, en su lugar, sugiero una aproximación cercana que se detendrá dentro de las 100 iteraciones para pasar el límite sqrt, y también mostrar actualizaciones de estado regularmente.

if (num%2 == 0) 
{ 
    flag=0; 
    return flag; 
} 

/* Now that we checked 2, we only need to check odd numbers from now on. */ 
for(i=3;i<num;i+=2) 
{ 
    if (i%101 == 0) 
    { 
     printf("i is %d out of %d\n", i, num); 
     if (i*i > num) 
     { 
      break; /* If you pass the sqrt boundary, quit. */ 
     } 
    } 

    if(num%i==0) 
    { 
     flag=0; 
     break; 
    } 
} 

---

P. S. Pongo este código en un proyecto de C# (transferencia menor). De acuerdo, ahora se ejecutaba en un sistema operativo de 64 bits, con un mejor compilador y una CPU de 2,8 GHz.
Se ejecutó en menos de 20 segundos.

Answer 8

puede utilizar métodos de tamizado para hacer esto también que no son mucho más complicados que lo que está utilizando. La idea es elegir los primeros n números primos consecutivos y usarlos para construir un tamiz. Lo discuto (con pruebas) en my answer a otra pregunta y Sheldon L. Cooper proporciona una implementación en his. No creo que haya obtenido suficientes votos ascendentes por hacerlo (ya recibí 'buena respuesta', así que tal vez podrías ayudarlo con eso.

así que después de calcular los números de tamiz, solo necesitas probar la divisibilidad por números que se alinean con el tamiz y son más pequeños que la raíz cuadrada de n.

Answer 9

Como han dicho otros: comprobar los límites de su aplicación

Si TurboC++ tiene <limits.h>, los límites de aplicación tienen una macro correspondiente definido en esa cabecera

#include <limits.h> 
#include <stdio.h> 
int main(void) { 
    printf("int goes from %d to %d.\n", INT_MIN, INT_MAX); 
    printf("long goes from %ld to %ld.\n", LONG_MIN, LONG_MAX); 
    return 0; 
} 

Si eso falla, necesita "calcular" los límites usted mismo. Estoy cambiando a unsigned porque no hay problema de desbordamiento con ellos, y sólo necesita "calcular" el límite superior (el límite inferior es 0)

#include <stdio.h> 
int main(void) { 
    unsigned u; 
    unsigned long lu; 

    u = -1; lu = -1; 
    printf("unsigned ints go all the way to %u\n", u); 
    printf("unsigned longs go all the way to %lu\n", lu); 
    return 0; 
} 

---

En mi sistema, las salidas 1er programa

int goes from -2147483648 to 2147483647. 
long goes from -9223372036854775808 to 9223372036854775807.

y el segundo programa de salidas

unsigned ints go all the way to 4294967295 
unsigned longs go all the way to 18446744073709551615

Answer 10

Aún no hay comentario/respuesta acerca º e constante excepto un "Epic" ...

#define TWO_MILLION 2*1000*1000 

Esto es malo. Cuando se cambia el valor más adelante, que o bien tienen un nombre de contenido-desajuste:

#define TWO_MILLION 5*1000*1000 

o se cambia el nombre a

#define FIVE_MILLION 5*1000*1000 

y hay que cambiar todo el mundo lo ha usado. No nombre sus constantes después del contenido, esto solo convierte sus números mágicos en nombres mágicos. Nómbrelos según su significado, p. MAX_NUMBERUPPER_LIMITRANGE_TO_TEST o lo que mejor se adapte.