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:
#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:
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.
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:
#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 ;
}
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:
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.
Autor
En línea
