Encuentra el número primo número 10000

Este es mi código para encontrar el número primo número 10000, pero es realmente lento, toma 7 segundos calcularlo.

#include  #include  long int prime (int n) { int i; for(i=2;i<n;i++) { if(n%i==0) return 0; } return 1; } int main() { int i=2,counter=0; while(1) { if(prime(i)) counter++; if(counter==10000) break; i++; } printf("10000th prime number is: %d",i); } 

Es un método de fuerza bruta, por lo que probablemente sea un motivo tan lento. Creo que el problema puede ser que tiene que llamar a la función tantas veces. Entonces, ¿qué crees que puede optimizarse o es mejor encontrar alguna fórmula matemática para esto?

Puede reducir el tiempo sustancialmente haciendo los siguientes cambios para prime() :

  1. Parando en sqrt(n) .
  2. Comenzando en i=3 , e incrementando i en 2 .

Aquí hay un progtwig que contiene ambas versiones y el tiempo empleado por cada una.

 #include  #include  #include  #include  int is_prime1 (int n) { int i; for(i=2;i 

Ejecución de la muestra:

 ./test 10000 

Salida de muestra:

 10000th prime number is: 104729 Time taken: 9.469000 10000th prime number is: 104729 Time taken: 0.078000 

Para optimizar un poco su código (los cambios se realizan en función de los comentarios):

 long int prime (int n) { int i; int e = (int)sqrt(n); for(i=2; i<=e;i++) { if(n%i==0) return 0; } return 1; } 
 #include  #include  #include  int *prime; int prime_n; void make_prime_table(int n){ prime = malloc(sizeof(int) * n / 2); prime_n =0; prime[prime_n++] = 2; prime[prime_n++] = 3; int i, j; for(i = 5; i <= n; i +=2){ bool is_prime = true; for(j = 1; j < prime_n ; ++j){ int t = prime[j]; if(t * t > i) break; if(i % t == 0){ is_prime = false; break; } } if(is_prime) prime[prime_n++] = i; } } int main(void){ int n = 105000; make_prime_table(n); if(prime_n >= 10000) printf("10000th prime number is: %d\n", prime[9999]); free(prime); return 0; }