elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Los 10 CVE más críticos (peligrosos) de 2020


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  [Aporte] Detector de números primos en C++
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: 1 [2] Ir Abajo Respuesta Imprimir
Autor Tema: [Aporte] Detector de números primos en C++  (Leído 8,337 veces)
leosansan


Desconectado Desconectado

Mensajes: 1.314


Ver Perfil
Re: [Aporte] Detector de números primos en C++
« Respuesta #10 en: 11 Agosto 2014, 21:03 pm »

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

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
  1. 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! ..... !!!!




« Última modificación: 11 Agosto 2014, 22:04 pm por leosansan » En línea

kutcher

Desconectado Desconectado

Mensajes: 53


Ver Perfil
Re: [Aporte] Detector de números primos en C++
« Respuesta #11 en: 12 Agosto 2014, 02:09 am »

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

Código
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4.  
  5. #define MAXIMO 100000000
  6.  
  7. using namespace std;
  8.  
  9. bool es_primo[MAXIMO] = {0};
  10. vector<int> primos;
  11.  
  12. void primo(int limite);
  13. void cargarPrimos(int limite);
  14.  
  15. int main(void)
  16. {
  17.    primo(MAXIMO);
  18.    //cargarPrimos(MAXIMO);
  19.  
  20.    return 0;
  21. }
  22.  
  23. void cargarPrimos(int limite)
  24. {
  25.    primos.push_back(2);
  26.    primos.push_back(3);
  27.  
  28.    for (int i = 5; i < limite; i++)
  29.    {
  30.        if (es_primo[i])
  31.        {
  32.            primos.push_back(i);
  33.        }
  34.    }
  35. }
  36. void primo(int limite)
  37. {
  38.    int raiz = ceil(sqrt(limite));
  39.  
  40.    for (int x = 1; x <= raiz; x++)
  41.    {
  42.       for (int y = 1; y <= raiz; y++)
  43.       {
  44.         int n = (4 * x * x) + (y * y);
  45.         if (n <= limite && (n % 12 == 1 || n % 12 == 5))
  46.            es_primo[n] = 1;
  47.         n = (3 * x * x) + (y * y);
  48.         if (n <= limite && n % 12 == 7)
  49.            es_primo[n] = 1;
  50.         n = (3 * x * x) - (y * y);
  51.         if (x > y && n <= limite && n % 12 == 11)
  52.            es_primo[n] = 1;
  53.        }
  54.    }
  55. }
  56.  



  


« Última modificación: 12 Agosto 2014, 02:12 am por kutcher » En línea

leosansan


Desconectado Desconectado

Mensajes: 1.314


Ver Perfil
Re: [Aporte] Detector de números primos en C++
« Respuesta #12 en: 12 Agosto 2014, 06:33 am »

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
  1. for (int i = 3 ; i < limite ; i++)
  2.        if ( es_primo [ i ] )
  3.            cont++ , primos.push_back ( i ) ;

Aún poniendo un:

Código
  1. for ( int i = 0 ; i < cont ; i++ )
  2.      cout << primos [ i ] << "  "  ;
  3.    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
  1. .............................................
  2.            es_primo [ n ] = true;
  3. ....................................
  4.          es_primo  [ b ] = false;
  5. ................................

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! ..... !!!!


En línea

Páginas: 1 [2] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
[APORTE] numeros primos
Java
Caballero Maldito 1 2,686 Último mensaje 2 Diciembre 2009, 21:27 pm
por Blitzkrieg'
[Python 2.6] Funcion generadora de Numeros primos (5.761.455 primos en 19 seg)
Scripting
katas 2 9,503 Último mensaje 10 Marzo 2010, 01:50 am
por Novlucker
NUMEROS PRIMOS
Programación C/C++
alviera 4 5,662 Último mensaje 7 Diciembre 2010, 06:39 am
por N0body
[Aporte] javascript - Proporción de números
Desarrollo Web
TickTack 6 3,592 Último mensaje 14 Enero 2021, 10:38 am
por #!drvy
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines