Probé este problema del Proyecto Euler donde necesito calcular la suma de todos los números primos hasta dos millones.
Esta es la solución que he encontrado -
#include <stdio.h> int main() { long sum = 5; // Already counting 2 and 3 in my sum. int i = 5; // Checking from 5 int count = 0; while (i <= 2000000) { count = 0; for (int j = 3; j <= i / 2; j += 2) { // Checking if i (starting from 5) is divisible from 3 if (i % j == 0) { // to i/2 and only checking for odd values of j count = 1; } } if (count == 0) { sum += i; } i += 2; } printf("%ld ", sum); }Se tarda alrededor de 480 segundos en ejecutarse y me preguntaba si había una mejor solución o consejos para mejorar mi programa.
________________________________________________________ Executed in 480.95 secs fish external usr time 478.54 secs 0.23 millis 478.54 secs sys time 1.28 secs 6.78 millis 1.28 secsCon dos pequeñas modificaciones, su código se vuelve mucho más rápido:
#include <stdio.h> #include <math.h> int main() { long long sum = 5; // we need long long, long might not be enough // depending on your platform int i = 5; int count = 0; while (i <= 2000000) { count = 0; int limit = sqrt(i); // determine upper limit once and for all for (int j = 3; j <= limit; j += 2) { // use upper limit sqrt(i) instead if i/2 if (i % j == 0) { count = 1; break; // break out from loop as soon // as number is not prime } } if (count == 0) { sum += i; } i += 2; } printf("%lld ", sum); // we need %lld for long long }Todas las explicaciones están en los comentarios.
Pero ciertamente hay formas mejores e incluso más rápidas de hacer esto.
Ejecuté esto en mi MacPro de 10 años y para los 20 millones de primeros números primos tomó alrededor de 30 segundos.
Este programa calcula casi al instante (incluso en Depuración...) la suma de 2 millones, solo necesita un segundo para 20 millones (Windows 10, i7 de 10 años a 3,4 GHz, MSVC 2019).
Nota: No tuve tiempo de configurar mi compilador C, es por eso que hay un molde en el malloc .
La optimización "grande" es almacenar valores cuadrados Y números primos, por lo que no se prueba absolutamente ningún divisor imposible. Dado que no hay más de 1/10 de números primos dentro de un intervalo entero dado (heurística, un código robusto debería probar eso y reasignar la matriz de primes cuando sea necesario), el tiempo se reduce drásticamente.
#include <stdio.h> #include <malloc.h> #define LIMIT 2000000ul // Computation limit. typedef struct { unsigned long int p ; // Store a prime number. unsigned long int sq ; // and its square. } prime ; int main() { prime* primes = (prime*)malloc((LIMIT/10)*sizeof(*primes)) ; // Store found primes. Can quite safely use 1/10th of the whole computation limit. unsigned long int primes_count=1 ; unsigned long int i = 3 ; unsigned long long int sum = 0 ; unsigned long int j = 0 ; int is_prime = 1 ; // Feed the first prime, 2. primes[0].p = 2 ; primes[0].sq = 4 ; sum = 2 ; // Parse all numbers up to LIMIT, ignoring even numbers. // Also reset the "is_prime" flag at each loop. for (i = 3 ; i <= LIMIT ; i+=2, is_prime = 1 ) { // Parse all previously found primes. for (j = 0; j < primes_count; j++) { // Above sqrt(i)? Break, i is a prime. if (i<primes[j].sq) break ; // Found a divisor? Not a prime (and break). if ((i % primes[j].p == 0)) { is_prime = 0 ; break ; } } // Add the prime and its square to the array "primes". if (is_prime) { primes[primes_count].p = i ; primes[primes_count++].sq = i*i ; // Compute the sum on-the-fly sum += i ; } } printf("Sum of all %lu primes: %llu\n", primes_count, sum); free(primes) ; }Su programa se puede mejorar fácilmente deteniendo el ciclo interno antes:
sqrt(j) i También tenga en cuenta que el tipo long podría no ser lo suficientemente grande para la suma en todas las arquitecturas. Se recomienda long long .
Aquí hay una versión modificada:
#include <stdio.h> int main() { long long sum = 5; // Already counting 2 and 3 in my sum. long i = 5; // Checking from 5 while (i <= 2000000) { int count = 0; for (int j = 3; j * j <= i; j += 2) { // Checking if i (starting from 5) is divisible from 3 if (i % j == 0) { // to i/2 and only checking for odd values of j count = 1; break; } } if (count == 0) { sum += i; } i += 2; } printf("%lld\n", sum); }¡Este simple cambio reduce drásticamente el tiempo de ejecución! Es más de 1000 veces más rápido para 2000000:
chqrlie> time ./primesum 142913828922 real 0m0.288s user 0m0.264s sys 0m0.004sSin embargo, tenga en cuenta que la división de prueba es mucho menos eficiente que el tamiz clásico de Eratóstenes.
Aquí hay una versión simplista:
#include <stdio.h> #include <stdlib.h> int main() { long max = 2000000; long long sum = 0; // Allocate an array of indicators initialized to 0 unsigned char *composite = calloc(1, max + 1); // For all numbers up to sqrt(max) for (long i = 2; i * i <= max; i++) { // It the number is a prime if (composite[i] == 0) { // Set all multiples as composite. Multiples below the // square of i are skipped because they have already been // set as multiples of a smaller prime. for (long j = i * i; j <= max; j += i) { composite[j] = 1; } } } for (long i = 2; i <= max; i++) { if (composite[i] == 0) sum += i; } printf("%lld\n", sum); free(composite); return 0; }Este código es otras 20 veces más rápido para 2000000:
chqrlie> time ./primesum-sieve 142913828922 real 0m0.014s user 0m0.007s sys 0m0.002sEl enfoque de tamiz se puede mejorar aún más de muchas maneras para límites más grandes.