Necesita ayuda para optimizar el algoritmo: sum de todos los números primos menores de dos millones

Estoy tratando de hacer una pregunta del Proyecto Euler .

Estoy buscando la sum de todos los números primos por debajo de 2,000,000.

Esto es lo que tengo…

int main(int argc, char *argv[]) { unsigned long int sum = 0; for (unsigned long int i = 0; i  %lu\n", sum); } int isPrime(int num) { if (num < 2) { return 0; } for (int i = 2; i < num; ++i) { if (num % i == 0) { return 0; } } return 1; } 

Lleva mucho tiempo ejecutarse, por lo tanto, no cumple con la regla de un minuto de tiempo de ejecución para los problemas de Euler.

Cuando lo ejecuto con el límite de 10, obtiene la respuesta correcta, 17 como en la pregunta.

Mi conjetura es que hay algún algoritmo que puede reducir el trabajo que se está haciendo. El problema es que no sé qué es.

¿Puede alguien indicarme el camino correcto?

Gracias.

Con i de 2 a 2000000 (o cualquier límite superior), una vez que determine que i es primo, entonces sabrá que {2i, 3i, 4i, ..., ni} no son números primos, donde ni <= 2000000 .

No necesitas probar esos números, sabes que no son primos.

A medida que avanza a través de su serie de testNumbers de testNumbers y elimina números de esta lista, los números que ahora sabe no son primos, reduce significativamente los números que realmente necesita probar.

Sí, este es el Tamiz de Eratóstenes.

Puedes acortar el tiempo que buscas para obtener el número primo. Hay millones de maneras de hacerlo. Creo que no es necesario realizar pruebas hasta num, sino solo a sqrt (num), pero esto solo le ayudará un poco (en los números primos reales)

Existen métodos estadísticos para verificar si un número primo es realmente primo, que es más rápido y solo se puede confundir una vez en 2 ^ mucho …

Un investigador de la India encontró la forma más rápida de encontrar un número primo, pero no puedo encontrar el enlace.

También puedes mirar aquí:

Wiki

Puede acelerar su función isPrime(int num) pasando la matriz de números primos descubiertos hasta ahora y verificar si num es un múltiplo de estos números primos. Además, no es necesario realizar un bucle hasta num , solo sqrt(num) .

Use el tamiz de Atkin, es una versión optimizada del tamiz de enlace Eratosthenes.

Sugerencia: Utilice BitArray y seive método.

Vea el código si no puede resolverlo. El código está en Java pero no sería difícil traducirlo a C.

 #include  #include  #include  struct prime_list_t { long n; struct prime_list_t *next; }; void add_prime_list_t(struct prime_list_t** list, long n); void free_prime_list_t(struct prime_list_t** list); long count_prime_list_t(struct prime_list_t* list); long last_prime_list_t(struct prime_list_t* list); /* if one of the primes in list divides n, is not a prime */ int is_prime(struct prime_list_t* pl, long n) { struct prime_list_t* p; if(pl == NULL) { abort(); } p = pl; while(p != NULL) { if(n % p->n == 0) { return 1; } p = p->next; } return 0; } int main() { struct prime_list_t* pl = NULL; struct prime_list_t* p; long n_up = 2000000; long long p_sum = 0; long ppr; int done; /* add first prime number */ add_prime_list_t(&pl, 2); /* from now on add to this list up to the number of items */ done = 0; do { /* get the last prime plus one */ ppr = last_prime_list_t(pl) + 1; while(is_prime(pl, ppr) != 0) { ppr++; if(ppr >= n_up) { /* hit the upper limit */ done = 1; break; } } if(done) { break; } /* ppr is prime */ add_prime_list_t(&pl, ppr); /* display status */ printf("%ld numbers largest prime %ld\r", count_prime_list_t(pl), last_prime_list_t(pl)); } while(!done); p = pl; p_sum = 0; while(p) { // printf("%d ", p->n); p_sum += p->n; p = p->next; } printf("\nsum: %I64d\n", p_sum); free_prime_list_t(&pl); return 0; } void add_prime_list_t(struct prime_list_t** list, long n) { struct prime_list_t* node; if(list == NULL) { abort(); } node = (struct prime_list_t*)malloc(sizeof(struct prime_list_t)); if(node == NULL) { abort(); } node->n = n; node->next = NULL; if(*list == NULL) { *list = node; } else { struct prime_list_t* p; p = *list; while(p->next != NULL) { p = p->next; } p->next = node; } } void free_prime_list_t(struct prime_list_t** list) { struct prime_list_t* node; if(list == NULL) { return; } node = *list; while(node != NULL) { struct prime_list_t* p; p = node; node = node->next; free(p); } *list = NULL; } long count_prime_list_t(struct prime_list_t* list) { long c; struct prime_list_t* p; for(p = list, c = 0; p != NULL; p = p->next, c++) ; return c; } long last_prime_list_t(struct prime_list_t* list) { long n; struct prime_list_t* p; n = 0; p = list; while(p->next != NULL) { p = p->next; } return p->n; } 

Y esta sería la salida:

 $kpwr 148933 numbers largest prime 1999993 sum: 142913828922 $ 

Para referencia (si está aquí, entonces ya está tratando de buscar la respuesta), cito a Lucy_Hedgehog (en el Equipo de Desarrollo para PE):

Aquí hay una solución que es más eficiente que el tamiz de Eratóstenes. Se deriva de algoritmos similares para contar primos . La ventaja es que no hay necesidad de encontrar todos los números primos para encontrar su sum.

La idea principal es la siguiente: Sea S (v, m) la sum de los enteros en el rango 2..v que permanece después del cribado con todos los números primos más pequeños o iguales que m. Eso es S (v, m) es la sum de enteros hasta v que son primos o el producto de primos mayores que m.

S (v, p) es igual a S (v, p-1) si p no es primo o v es más pequeño que p * p. De lo contrario (p prime, p * p <= v) S (v, p) se puede calcular a partir de S (v, p-1) encontrando la suma de los enteros que se eliminan mientras se tamiza con p. Se elimina un entero en este paso si es el producto de p con otro entero que no tiene un divisor más pequeño que p. Esto se puede expresar como

$ S (v, p) = S (v, p-1) – p (S (v / p, p-1) – S (p-1, p-1)).

La progtwigción dinámica puede ser utilizada para implementar esto. Es suficiente calcular S (v, p) para todos los enteros positivos v que se pueden representar como piso (n / k) para algún entero k y todos $ p \ leq \ sqrt v $.

 def P10(n): r = int(n**0.5) assert r*r <= n and (r+1)**2 > n V = [n//i for i in range(1,r+1)] V += list(range(V[-1]-1,0,-1)) S = {i:i*(i+1)//2-1 for i in V} for p in range(2,r+1): if S[p] > S[p-1]: # p is prime sp = S[p-1] # sum of primes smaller than p p2 = p*p for v in V: if v < p2: break S[v] -= p*(S[v//p] - sp) return S[n] 

La complejidad de este algoritmo es de aproximadamente $ O (n ^ {0.75}) $ y necesita 9 ms para encontrar la solución.

Las ideas son similares a encontrar sum sumria y es una aplicación del método de hipérbola de Dirichlet .

si puede manejar la prueba de case para 2 , inicie el bucle a partir de tres y coloque i+=2 lugar de i++ reduciendo la iteración del bucle a la mitad