[Aporte] Detector de números primos en C++

[leosansan]

leosansan tu programa no imprime la cantidad de primos requerida al ingresar 100 solo procesa 25 que son los que podemos encontrar entre 1 y 100 por eso es evidente la diferencia de velocidades sobre las soluciones anteriores

Es que en todos los códigos que comparé calculé los primos "hasta" N.

Aquí una salida para que lo veas:

Código (cpp) [Seleccionar] Expandir


Numero de primos a conseguir HASTA ( i >= N / 2 ) : 100
5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83
 89  97
       Conseguidos 25 primos en 0.01 segundos.

Numero de primos a conseguir HASTA ( i >= N / 2 ) : 1000
5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83
 89  97  101  103  107  109  113  127  131  137  139  149  151  157  163  167
173  179  181  191  193  197  199  211  223  227  229  233  239  241  251  257
263  269  271  277  281  283  293  307  311  313  317  331  337  347  349  353
359  367  373  379  383  389  397  401  409  419  421  431  433  439  443  449
457  461  463  467  479  487  491  499  503  509  521  523  541  547  557  563
569  571  577  587  593  599  601  607  613  617  619  631  641  643  647  653
659  661  673  677  683  691  701  709  719  727  733  739  743  751  757  761
769  773  787  797  809  811  821  823  827  829  839  853  857  859  863  877
881  883  887  907  911  919  929  937  941  947  953  967  971  977  983  991
997
       Conseguidos 168 primos en 0.063 segundos.



Como ves calcula los primos "hasta" n. Ya comenté al principio que había modificado el código inicial que si que calcula los "n" números primos. Me faltó corregir el código y poner:

Código (cpp) [Seleccionar] Expandir

cout << "Numero de primos a conseguir HASTA".........

Espero que ahora esté claro, siento no haber puesto el "HASTA" en el código. Ya edité el mensaje anterior y corregí ese detalle.

¡¡¡¡ Saluditos! ..... !!!!

[kutcher]

Hago un aporte con otro método bastante rápido :

Código (cpp) [Seleccionar] Expandir

#include <iostream>
#include <cmath>
#include <vector>

#define MAXIMO 100000000

using namespace std;

bool es_primo[MAXIMO] = {0};
vector<int> primos;

void primo(int limite);
void cargarPrimos(int limite);

int main(void)
{
   primo(MAXIMO);
   //cargarPrimos(MAXIMO);

   return 0;
}

void cargarPrimos(int limite)
{
   primos.push_back(2);
   primos.push_back(3);

   for (int i = 5; i < limite; i++)
   {
       if (es_primo[i])
       {
           primos.push_back(i);
       }
   }
}
void primo(int limite)
{
   int raiz = ceil(sqrt(limite));

   for (int x = 1; x <= raiz; x++)
   {
      for (int y = 1; y <= raiz; y++)
      {
        int n = (4 * x * x) + (y * y);
        if (n <= limite && (n % 12 == 1 || n % 12 == 5))
           es_primo[n] = 1;
        n = (3 * x * x) + (y * y);
        if (n <= limite && n % 12 == 7)
           es_primo[n] = 1;
        n = (3 * x * x) - (y * y);
        if (x > y && n <= limite && n % 12 == 11)
           es_primo[n] = 1;
       }
   }
}




 

[leosansan]

Hago un aporte con otro método bastante rápido :

´´´´´´´´´´´´´´´´´´´´´´´´´´´´´´´´´´´´

Conste que es en plan buen rollo, ¿vale?. 

No sé cuan rápido es porque de entrada tienes desactivado el "cargarPrimos".

No imprime nada por lo que no se sabe si calcula el total de primos hasta n o los n primeros primos. Viendo un poco el código, por aquello de que x e y varían de 1 a la raíz del limite, creo que es lo primero. Pero en este caso te faltaría una variable tipo acumulador que vaya contando cuántos primos van saliendo Creo que podría ser algo como:

Código (cpp) [Seleccionar] Expandir

for (int i = 3 ; i < limite ; i++)
        if ( es_primo [ i ] )
            cont++ , primos.push_back ( i ) ;

Aún poniendo un:

Código (cpp) [Seleccionar] Expandir

for ( int i = 0 ; i < cont ; i++ )
      cout << primos [ i ] << "  "  ;
    cout << endl << "Hasta " << MAXIMO << " hay "  << cont ;

no obtengo los resultados esperados,  ¿puedes confirmarlo, please?.

Tienes varios if en la función primo, ¿seguro que con ellos recorres todos los números de 1 a limite?,  porque si no es así faltaría un ultimo else.

Como diría eferion, me he levantado "quisquilloso" y como la función "es_primo" es de tipo bool sus asignaciones propiamente sería de tipo:

Código (cpp) [Seleccionar] Expandir

.............................................
            es_primo [ n ] = true;
....................................
          es_primo  [ b ] = false;
................................

Sí, ya sé que con el 1 y el cero va, pero es por usar true y false,así se manifiesta claramente que es de tipo bool no sea que en otro momento nos despistemos y hagamos es_primo  [ b ] = 97 o cosas por el estilo.

Quedo a la espera de las mejoras y de un código realmente funcional para pasarle el test de los tiempos, aunque con el uso tan extenso que haces de las operaciones módulo ya me imagino los resultados.

En cualquier caso, y caso de que funcione adecuadamente, será un aporte "diferente" y por ello muy bienvenido. 

Y reitero lo del principio, en plan buen rollo, ¿vale?. 

¡¡¡¡ Saluditos! ..... !!!!