Holas :D
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
#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
Cita de: ivancea96 en 10 Agosto 2014, 13:50 PM
Holas :D
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.
(http://i1280.photobucket.com/albums/a497/leosansan/leosan1/leones%20peques/lion14peque_zps1d213b80.jpg)
EDITADO con
"HASTA" en la impresión, para que no queden dudas.
Y aprobecho el mismo hilo para colgar este factorizador de números:
#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;
}
}
Respecto del código de los números primos se te pasó actualizar los include:
#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.
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.
Cita de: ivancea96 en 11 Agosto 2014, 14:49 PM
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. :o
A ver si alguien más se anima a comprobarlo.
¡¡¡¡ Saluditos! ..... !!!!
(http://st.forocoches.com/foro/images/smilies/aaaaa.gif)
Con 100, significa 100 primos eh?
Cita de: ivancea96 en 11 Agosto 2014, 15:06 PM
Con 100, significa 100 primos eh?
¡Ah!, menuda pifia la mia, :laugh:
Por cierto en el código de factorizar se te ha escapado un "=" , no estaba en:
for(;i<=sq;)Sin el igual factoriza 100 como:
Pon el numero a factorizar: 100
Numero a factorizar: 100
1 2 2 25
Acabado.
Y con el igual:
Pon el numero a factorizar: 100
Numero a factorizar: 100
1 2 2 5 5
Acabado.
Estoy al loro, ¿eh?. :laugh:
¡¡¡¡ Saluditos! ..... !!!!
(http://st.forocoches.com/foro/images/smilies/aaaaa.gif)
EDITO:
Seguro que lo has hecho a bote pronto ya que si lo piensas un poco el for que propones:
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: :o
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". :rolleyes:
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.
Cita de: leosansan en 11 Agosto 2014, 15:00 PM
E insisto, y perdón por ello, al introducir 100 me escribe en el fichero hasta el 547. :o
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
Cita de: leosansan en 11 Agosto 2014, 15:13 PM
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". :rolleyes:
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.
Cita de: kutcher en 11 Agosto 2014, 20:14 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:
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:
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! ..... !!!!
(http://st.forocoches.com/foro/images/smilies/aaaaa.gif)
Hago un aporte con otro método bastante rápido :
#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;
}
}
}
Cita de: kutcher en 12 Agosto 2014, 02:09 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:
for (int i = 3 ; i < limite ; i++)
if ( es_primo [ i ] )
cont++ , primos.push_back ( i ) ;Aún poniendo un:
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:
.............................................
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! ..... !!!!
(http://st.forocoches.com/foro/images/smilies/aaaaa.gif)