Necesita ayuda para optimizar el algoritmo - suma de todos los números primos por debajo de dos millones

Question

Estoy tratando de hacer una pregunta Project Euler.

Estoy buscando la suma 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 < 2000000; i++) { 


     if (isPrime(i)) { 
      sum += i; 
     } 
    } 

    printf("sum => %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; 
} 

Se lleva mucho tiempo, para ejecutar, por lo tanto, no satisface la regla de un minutos a 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.

Supongo que hay algún algoritmo que puede reducir el trabajo realizado. El problema es que no sé qué es.

¿Puede alguien señalarme en la dirección correcta?

Gracias.

Answer 1

Con i2-2000000 (o cualquier límite superior), una vez que se determina que i es primo, entonces sabemos que {2i, 3i, 4i, ..., ni} no son números primos, donde ni <= 2000000.

No es necesario que pruebe esos números; usted sabe que no son primos.

A medida que avanza en su matriz de testNumbers y elimina los números de esta lista, los números que ahora sabe que no son primos, reduce significativamente los números que realmente necesita para probar.

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

Answer 2

puede acortar el tiempo que busca el número principal. hay millones de formas de hacerlo. Creo que no necesita probar hasta num, pero solo en 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 en realidad primos que son más rápidos y solo se pueden confundir una vez en 2^mucho ...

La forma más rápida de encontrar el número primo fue encontrada por un investigador de India, pero no encuentro el enlace.

también se puede ver aquí:

Wiki

Answer 3

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

Answer 4

Utilice el tamiz de Atkin, es una versión optimizada del tamiz de Eratosthenes link.

Answer 5

Sugerencia: Utilice el método BitArray y seive.

Consulte code si no puede resolverlo.El código está en Java, pero no sería difícil de traducir a C.

Answer 6

#include <windows.h> 
#include <stdio.h> 
#include <stdlib.h> 

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 este sería el resultado:

$kpwr 
148933 numbers largest prime 1999993 
sum: 142913828922 

$ 

Answer 7

si se puede controlar la prueba case para 2 continuación de inicio del bucle de tres y poner i+=2 en lugar de reducir i++ iteración del bucle por medio

Answer 8

Como referencia (si está aquí, es que ya está tratando de buscar la respuesta), que quote Lucy_Hedgehog (en la Developmen t Equipo para PE):

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

La idea principal es como sigue: Sea S (v, m) será la suma de números enteros en el 2..v gama que permanecen después de tamizar con todos los primos menor o igual que m. Es decir, S (v, m) es la suma 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 principal ov es menor 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 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 menor que p. Esto puede ser expresado como

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

La programación dinámica se puede utilizar para implementar esto. Es suficiente con calcular S (v, p) para todos los enteros positivos v representables como piso (n/k) para un número entero ky 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.