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

[ivancea96]

Holas

Aquí dejo un código, más que nada curioso, que va guardando números primos en un archivo.

Información:

• Tras cerrar el programa, retoma el último primo que generó
• Funcionalidad para medir el tiempo que tarda (véase que con números altos empieza a tardar mucho más)
• Se usa sólo la librería estándar

Código (cpp) [Seleccionar] Expandir

#include <iostream>
#include <fstream>
#include <ctime>
#include <cmath>

using namespace std;

inline bool primo(uint64_t n){
   if(n%2==0) return false;
   uint64_t i=3;
   uint64_t sq = sqrt(n);
   for (;n%i!=0; i+=2){
       if(i>sq){
           i=n;
           break;
       }
   }
   return i==n;
}

int main () {
   while(true){
       uint64_t u=2, g=0, h=0;
       string t;
       cout << "Numero de primos a conseguir (0 para ver ultimo primo): ";
       getline(cin,t);
       g = strtoull(t.c_str(),NULL,0);
       ifstream leer("primos.txt", ios::ate);
       char n='0';
       if(leer){
           while(n!='\n'){
               leer.unget();
               n = leer.get();
               leer.unget();
           }
           leer.get();
           leer >> u;
       }
       leer.close();
       if(g==0){
           cout << "Ultimo primo conseguido: " << u << endl << endl;
           continue;
       }
       ofstream escribir("primos.txt", ios::app);
       if(u==2){
           escribir << u--;
       }
       clock_t timer = clock();
       while(h<g){
           u+=2;
           if(primo(u)){
               escribir << endl << u;
               ++h;
           }
       }
       cout << endl << "Conseguidos " << h << " primos en " << ((clock()-timer)*1000)/CLOCKS_PER_SEC << " milisegundos." << endl << endl;
   }
}

El código creo yo que es fácil de entender. Se usa fstream para manejar el archivo de primos.

Quien le quiera mejorar el algoritmo para detectar los primos, está en su derecho, por supuesto.
Quien quiera guardar los primos en binario (8 bytes para uint64_t), puede hacer fácilmente la modificación.
Y hasta quien quiera, que le ponga una barra de carga jaja

Bueno, espero que a alguien le ayude.

Byes :3

[leosansan]

Holas

Aquí dejo un código, más que nada curioso, que va guardando números primos en un archivo.

Información:

• Tras cerrar el programa, retoma el último primo que generó
• Funcionalidad para medir el tiempo que tarda (véase que con números altos empieza a tardar mucho más)
• Se usa sólo la librería estándar

Bueno, espero que a alguien le ayude.

Espero que no te moleste que modifique un poco el código para hacer uso del mismo en una comparativa entre distintos métodos y/o variantes para calcular los primos entre 1 y 10^2, 10^3, ......10^9.

El código que he usado para calcular los primos por el métode de "i*i=>n" e "i>=n/2" es:

Código (cpp) [Seleccionar] Expandir

#include <iostream>
#include <fstream>
#include <ctime>

using namespace std ;

inline bool primo ( uint64_t n ) {
   uint64_t i = 3 ;
   for ( ; n % i != 0 ; i += 2 )
       if ( i /** i >= n i*/ >= n / 2  )
           return true ;
   return false ;
}

int main ( ) {
   while ( true ) {
       uint64_t u = 1 , g = 0 , h = 0 ;
       clock_t t ;
       cout << "Numero de primos a conseguir HASTA " /*<< "( i * i >= N ) : " */<< "( i >= N / 2 ) : "  ;
       cin >> g ;
       t = clock ( ) ;
       while ( (u += 2) < g )
           if ( primo ( u ) )
               h++ ;
       t = clock ( ) - t ;
       cout << endl << "\tConseguidos " << h + 2 << " primos en " << ( ( float ) t ) / CLOCKS_PER_SEC << " segundos." << endl << endl ;
   }
}

Como se puede observar he eliminado el tema de guardar en fichero para calcular  tan sólo el tiempo para obtener los números primos.

Y estos son los resultados, en mi modesto ordenador, claro ( pongo el caso de "i*i>=N" y de "i>=N2" ya que son los que me interesan para  comparar  los resultados con el método del array primos:

Código (cpp) [Seleccionar] Expandir

Numero de primos a conseguir HASTA ( i >= N / 2 ) : 100

       Conseguidos 25 primos en 0 segundos.

Numero de primos a conseguir HASTA ( i >= N / 2 ) : 1000

       Conseguidos 168 primos en 0.001 segundos.

Numero de primos a conseguir HASTA ( i >= N / 2 ) : 10000

       Conseguidos 1229 primos en 0.038 segundos.

Numero de primos a conseguir HASTA ( i >= N / 2 ) : 100000

       Conseguidos 9592 primos en 2.887 segundos.

Numero de primos a conseguir HASTA ( i >= N / 2 ) : 1000000

       Conseguidos 78498 primos en 242.673 segundos.



Código (cpp) [Seleccionar] Expandir

Numero de primos a conseguir HASTA  ( i * i >= N ) : 100

 Conseguidos 25 primos en 0 segundos.

Numero de primos a conseguir HASTA ( i * i >= N ) : 1000

 Conseguidos 168 primos en 0 segundos.

Numero de primos a conseguir HASTA ( i * i >= N ) : 10000

 Conseguidos 1229 primos en 0.002 segundos.

Numero de primos a conseguir HASTA ( i * i >= N ) : 100000

 Conseguidos 9592 primos en 0.051 segundos.

Numero de primos a conseguir HASTA  ( i * i >= N ) : 1000000

 Conseguidos 78498 primos en 0.904 segundos.

Numero de primos a conseguir HASTA  ( i * i >= N ) : 10000000

 Conseguidos 664579 primos en 25.575 segundos.

Numero de primos a conseguir HASTA (  i * i >= N N ) : 100000000

 Conseguidos 5761455 primos en 696.361 segundos.





Como puede apreciarse hay una sutil ventaja del "i*i>=n" frente al "i>=n/2", hasta tal punto que para éste último no he tenido paciencia en ver en qué tiempo calcula los primos hasta 10^7.  Observar la enorme diferencia en el cálculo de los primos hasta 10^7, no te cuento si se introducen valores mayores.

Pero a lo que realmente iba era a comparar los métodos anteriores con una variante consistente en ir guardando los primos calculados en cada iteración. Como ya comenté en otro hilo este método presenta la ventaja que al usar los primos calculados se evita el probar todos los impares como posibles divisores de un número, tan sólo tiene que comparar con los primos que, evidentemente, son menos que los impares . Y como un resultado vale más que mil palabras paso a poner el código que he usado y el resultado obtenido:

Código (cpp) [Seleccionar] Expandir

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>

int main ( ) {
 int i = 0, n , k = 0 , x = 0 , N , lineas = 0 , N_PRIMS ;
 int potencias [ ] = { 5 , 10 , 100 , 1000 , 10000 , 100000 , 1000000 , 10000000 , 100000000 , 1000000000 } ;
 int Relacion, relacion [ ] = { 1 , 2 , 4 , 5 , 8 , 10 , 12 , 15 , 17 , 19 } ;
 char cifra [ 10 ] , cad1 [ ] = "%" , cad2 [] = "d" ;
 clock_t t ;
 while ( 1 ) {
   bool aux = false ;
   x = k = lineas = 0 ;
   printf ( "\n\nNumero de primos a conseguir HASTA : " ) ;
   scanf ( "%d" , &N ) ;

   for ( i = 0; i < 10; i++ )
     if ( N / potencias[i] >= 1 && N / potencias[i] < 10 ){
       Relacion = relacion [ i ] ;
       break ;
     }
   N_PRIMS = ( N / Relacion ) ;
   int *primos = calloc( N_PRIMS , sizeof ( unsigned int ) ) ;
   if ( !primos ) {
     printf ( "primos::No hay espacio suficiente en memoria" ) ;
     return EXIT_FAILURE ;
   }
   primos [ x++ ] = 2 ;
   primos [ x ] = 3 ;
   t = clock ( ) ;
   for ( n = 5 ; n <= N ; n += 2 ) {
     aux = false ;
     k = 1 ;
     for ( primos [ k ] ; primos [ k ] * primos [ k ] <= n ; k++ )
       if ( n % primos[k] == 0 ) {
         aux = true ;
         break ;
       }
     if ( !aux  )
       primos [ ++x ] = n ;
   }
   t = clock() - t ;
   printf ( "\n\t\t\tEl ultimo es: %d \n\n" , primos [ x ] );
   printf ( "Conseguidos los %d primos en %f segundos.\n\n" , x + 1, ( ( float ) t ) / CLOCKS_PER_SEC ) ;

        /***** PARA IMPRIMIR POR GRUPOS *****/

 /** quita el "+" que aparece al final de la siguiente linea  **/

 /*******************************+/
   int l = 1 , n1 = N ;
   for(  ;  n1 ; l ++, n1 /= 10 ) ;
   sprintf ( cifra , "%s%d%s" , cad1 , --l , cad2) ;
   for( n = 0 , i = 1 ; n <= x ; n ++ , i ++ ) {
     if( 90 / i == l )
       putchar ( '\n' ) , i = 1 , lineas++ ;
     if( lineas == 38 )
       system ( "pause" ) , lineas = 0 ;
     printf( cifra , primos [ n ] ) ;
   }
 /********************************/
   free ( primos ) ;
 }
 return EXIT_SUCCESS ;
}

Código (cpp) [Seleccionar] Expandir


Numero de primos a conseguir HASTA : 100

                       El ultimo es: 97

Conseguidos los 25 primos en 0.000000 segundos.



Numero de primos a conseguir HASTA: 1000

                       El ultimo es: 997

Conseguidos los 168 primos en 0.000000 segundos.



Numero de primos a conseguir HASTA: 10000

                       El ultimo es: 9973

Conseguidos los 1229 primos en 0.000000 segundos.



Numero de primos a conseguir HASTA: 100000

                       El ultimo es: 99991

Conseguidos los 9592 primos en 0.015000 segundos.



Numero de primos a conseguir HASTA: 1000000

                       El ultimo es: 999983

Conseguidos los 78498 primos en 0.151000 segundos.



Numero de primos a conseguir HASTA: 10000000

                       El ultimo es: 9999991

Conseguidos los 664579 primos en 3.721000 segundos.



Numero de primos a conseguir HASTA: 100000000

                       El ultimo es: 99999989

Conseguidos los 5761455 primos en 81.288000 segundos.





Creo que la "bondad=rapidez=eficiencia" de este método con respecto a los dos anteriores es más que evidente, basta observar el resultado para 10^8 de "696.361" segundos con el método de "i*i" frente a los "81.288000 " del método de los primos, así como los "25.575" de "i*i" frente a los escasos "3.721000" del método de los primos y la diferencia aumenta a medida que crecen el valor de "n".

Me permito una pequeña aclaración. En el último método he tenido que hacer "virguerías" con la memoria para alcanzar los valores de hasta 10^9. En realidad es sólo un parche ya que lo que procede es no guardar los primos en un array sino en un fichero, tal como propuso inicialmente ivancea96, pero como quería comparar los métodos mencionados no quería que la comparativa se viese afectada por el hecho de leer, guardar, leer en un fichero. No obstante dejo caer el que alguien se interese en implementar esa opción y la comparta con nosotros.  

Pero aquí no se acaban las opciones. Existen otras, en concreto me referiré a la llamada "Criba de Erastótenes", en la cual no se hace uso de la operación módulo lo que redunda en unos tiempos espectaculares respecto a los anteriores. Pongo algunos resultados con los anteriores métodos para que saquéis vuestras propias conclusiones:

Código (cpp) [Seleccionar] Expandir


Numero de primos a conseguir HASTA: 100

                       El ultimo es: 97

Conseguidos los 25 primos en 0.000000 segundos.


Numero de primos a conseguir HASTA: 1000

                       El ultimo es: 997

Conseguidos los 168 primos en 0.000000 segundos.


Numero de primos a conseguir HASTA: 10000

                       El ultimo es: 9973

Conseguidos los 1229 primos en 0.000000 segundos.


Numero de primos a conseguir HASTA: 100000

                       El ultimo es: 99991

Conseguidos los 9592 primos en 0.001000 segundos.


Numero de primos a conseguir HASTA: 1000000

                       El ultimo es: 999983

Conseguidos los 78498 primos en 0.018000 segundos.


Numero de primos a conseguir HASTA: 10000000

                       El ultimo es: 9999991

Conseguidos los 664579 primos en 0.181000 segundos.


Numero de primos a conseguir HASTA: 100000000

                       El ultimo es: 99999989

Conseguidos los 5761455 primos en 2.217000 segundos.


Numero de primos a conseguir HASTA: 1000000000

                       El ultimo es: 999999937

Conseguidos los 50847534 primos en 25.367000 segundos.





Ahora para 10^8 se pasa de los "696.361" segundos del "i*i" a los dos escasos segundos, "1.817000" del método de la Criba.  

Destaco que estos métodos son "caseros", es decir sin usar métodos matemáticos avanzados.

Espero que con lo anteriormente expuesto haya aclarado dudas que les surgió a algunos en otro hilo de primos.

Y ya "tá", un fuerte saludo para todos y sean benévolos con los posibles errores si los hubiera, todo ha sido con la mejor de las intenciones.

EDITADO con "HASTA" en la impresión, para que no queden dudas.

[ivancea96]

Y aprobecho el mismo hilo para colgar este factorizador de números:

Código (cpp) [Seleccionar] Expandir

#include <iostream>
#include <cmath>
#include <limits.h>

using namespace std;


int main () {
   while(true){
       unsigned long long int fin=0, i=2, hh=0;
       bool dos = true;
       cout << "Pon el numero a factorizar: ";
       cin >> hh;
       while(hh<2 || hh>ULLONG_MAX-1){
           cin.clear();
           cout << "Debe ser un numero entre 2 y 18446744073709551615: ";
           cin >> hh;
           cout << endl;
       }
       cout << endl << "Numero a factorizar: " << hh << endl << 1 << " ";
       uint64_t sq = sqrt(hh);
       for(;i<=sq;){
           if(hh%i==0)
               if(hh==i){
                   break;
               }else{
                   hh=hh/i;
                   sq = sqrt(hh);
                   cout << i << " ";
               }
           else
               if(dos){
                   dos=false;
                   ++i;
               }else
                   i+=2;
       }
       cout << hh << endl << "Acabado." << endl << endl << endl;
   }
}

[leosansan]

Respecto del código de los números primos se te pasó actualizar los include:

Código (cpp) [Seleccionar] Expandir

#include <iostream>
#include <fstream>
#include <ctime>
#include <cmath>
#include <cstdlib>

Pero no sé que pasa que después de introducir el número el programa se que en standby, supongo que por algún bucle. ¿No te pasa a ti?. Me pasa en Code::Blocks, no así en DeV-C++ donde si que funciona.  

Pues no, funciono una vez pero la segunda se queda también en standby, Me da que al escribir el fichero la primera vez va O.K pero al darle por segunda vez no va, vamos es como si no pudiera sobreescribir. Además al introducir n = 100 me escribe hasta el 547  

Un fuerte saludo y gracias por los aportes.

Por cierto, no abandones la idea del "concursillo", parecía interesante.

[ivancea96]

A mi me funciona perfecto el detector. Ahora mismo va por el millardo, y casi una GB de txt xD
Estoy planeando pasar de ascii a binario en archivo.

[leosansan]

A mi me funciona perfecto el detector. Ahora mismo va por el millardo, y casi una GB de txt xD
Estoy planeando pasar de ascii a binario en archivo.

Pues a mi la primera vez, es decir cuando aún no existe el fichero primos, sí que funciona, pero la segunda vez se "queda clavado".

E insisto, y perdón por ello, al introducir 100 me escribe en el fichero hasta el 547. 

A ver si alguien más se anima a comprobarlo.

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

[ivancea96]

Con 100, significa 100 primos eh?

[leosansan]

Con 100, significa 100 primos eh?

¡Ah!, menuda pifia la mia,  

Por cierto en el código de factorizar se te ha escapado un "=" , no estaba en:

Código (cpp) [Seleccionar] Expandir

for(;i<=sq;)

Sin el igual factoriza 100 como:

Código (cpp) [Seleccionar] Expandir



Pon el numero a factorizar: 100

Numero a factorizar: 100
1 2 2 25
Acabado.



Y con el igual:

Código (cpp) [Seleccionar] Expandir



Pon el numero a factorizar: 100

Numero a factorizar: 100
1 2 2 5 5
Acabado.



Estoy al loro, ¿eh?.  

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

EDITO:

   Seguro que lo has hecho a bote pronto ya que si lo piensas un poco el for que propones:

Código (cpp) [Seleccionar] Expandir

uint64_t sq = sqrt(hh);
       for(;i<=sq;){
           if(hh%i==0)
               if(hh==i){
                   break;
               }else{
                   hh=hh/i;
                   sq = sqrt(hh);
                   cout << i << " ";
               }
           else
               if(dos){
                   dos=false;
                   ++i;
               }else
                   i+=2;
       }

se puede reducir a tan sólo una línea:  

Código (cpp) [Seleccionar] Expandir

while ( i < hh )
 ( hh % i == 0 ) ? cout << i << " "  , hh /=  i : i = ( i == 2 ) ? i + 1 :i + 2 ;

sin necesidad de usar la variable "dos" ni "sqrt".  

Aquí es donde hecho de menos lo que has llamado "Concursillo" donde se plantee un problema y en sucesivas réplicas y/o contra réplicas podamos ir "puliendo" un código.

[kutcher]

E insisto, y perdón por ello, al introducir 100 me escribe en el fichero hasta el 547.  

A ver si alguien más se anima a comprobarlo.

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

[ivancea96]

Código (cpp) [Seleccionar] Expandir

while ( i < hh )
 ( hh % i == 0 ) ? cout << i << " "  , hh /=  i : i = ( i == 2 ) ? i + 1 :i + 2 ;

sin necesidad de usar la variable "dos" ni "sqrt".  

Aquí es donde hecho de menos lo que has llamado "Concursillo" donde se plantee un problema y en sucesivas réplicas y/o contra réplicas podamos ir "puliendo" un código.

Pues reserva esos comentarios para el concurso.
Usar 2 operadores ternarios en vez de if no hace el código más bonito.