Mensajes

[¡¡¡¡ Saluditos! ..... !!!!]

Tienes un problema con eso de empezar los for desde "1" ya que las posiciones del arrray van desde cero hasta TAM-1 de forma que el listado[4] = 12 se "sale" del tamaño del array que va de 0 a 3.

Vamos que sería:

Código (cpp) [Seleccionar] Expandir

************************************

listado[0] = 11;
listado[1] = 13;
listado[2] = 53;
listado[3] = 12;

********************************************

        for(int x = 0; x < TAM; x++)
          for(int s = 0; s < TAM-1; s++){

********************************************

for(int g = 0; g < TAM; g++)

********************************************
}


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

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

[¡¡¡¡ Saluditos! ..... !!!!]

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.

[¡¡¡¡ Saluditos! ..... !!!!]

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

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.

[Información:]

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]

no entendí lo que no estaba claro D: pero extiendo
.............................................................

Está claro que no me exprese bien, sorry!!!.

Yo no hablaba del caso de comprobar si "un" número concreto es o no primo sino de calcular  los números primos en un intervalo, como de 1  10^8, por ejemplo. Está claro que si sólo es un número es casi impepinable usar el método del módulo, y aún así se pueden introducir mejoras.

En cuanto al número de operaciones es al menos menor ya que lo único que se hace es sustituir la operación de "i*i<N" por "primos[ i ]*primos[ i ]<N". El motivo de que sea menor es que en el método del "i*i" se usan todos los impares desde 3 a la raíz del número en el peor de los casos, como en el caso de querer comprobar si 99991 es o no primo, sin embargo en el método del array sólo se usan los primos previamente  calculados que obviamente son menores que los impares. La única penalización es el uso de un array y que tampoco ya que lo que procede realmente es ir guardando los primos calculados en en fichero y escribir y leer los cuando proceda. Como ves, se consigue disminuir el número de operaciones módulo en unos cuantos miles, todo lo cual redunda en una mejora, al menos sobre el papel.

No obstante, y para que no digan que hago tareas, será en este otro hilo, cortesía de ivancea96 aporte_detector_de_numeros_primos_en_c donde podrás encontrar una comparativa de los métodos y donde se pone de manifiesto la bondad del método del uso de "primos" frente al "i*i"

Espero que ahora esté más claro.



Un fuerte saludo de León amigo engel lex.

[for]

...................................................
Buscando encontré que la instrucción de repetición for es usada para repetición por contador, mientras while es usada para repetición controlada por centinela. ¿Por qué es así?

Las instrucciones de repetición do...while para que es requerida? se para que sirve, pero no se para qué casos tiene un uso especial
..................................................

Dicho a lo breve:

* for: Cuando voy a realizar un número de iteraciones conocido de antemano. Caso típico  de su uso en el caso en que se pide al usuario ingresar 10 números. No obstante siempre se puede salir antes del bucle con "break", "return" o similar caso de que proceda, pero no es lo usual ya que en ese caso lo más lógico sería haber usado un while.

* while: Bucle a usar cuando no tiene por qué conocerse previamente el número de iteraciones, aunque también podría usarse en este caso el for con una salida del mismo con un break, return y/o bandera o flag. En cambio ahora lo que se conoce es una "condición" que se ha de cumplir para terminar el bucle. Caso típico en que el usuario ha de introducir datos hasta que entre un valor particular, en cuyo caso se sale del bucle.

* do-while: Básicamente es como el while sólo que sabemos de antemano que se va a producir una iteración al menos.

Esto a lo simple. Te aconsejaría un buen libro para ampliar conocimientos.   

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

[no hace nada]

El programa me compila perfectamente, pero al introducirle los números se para no hace nada y no encuentro el error, podrían ayudarme por favor:(
............................

En realidad si que hace, pero no termina. En el while, que por cierto está de más, no varías el valor de i con lo que el while provoca un  bucle infinito, tendrías que poner al final del mismo algo como i++.

Pero lo correcto es cambiar un poco esa función "minimo". Además de lo ya mencionado de que sobra el while, conviene pasarle como parámetro el valor de la variable nu ya que tal como lo tienes con MAX, y si has introducido un número de valores inferior al mismo, se estaría tomando posiciones de memoria no definidas con el consiguiente riesgo de que contengan basura y distorsione el valor calculado del mínimo. Y el valor de nu=' ' sobraría al pasar como argumento su valor.

Aunque se puede abreviar, la función "minimo" puede ser algo como:

Código (cpp) [Seleccionar] Expandir

int minimo ( nument Array , int nu) {
int minimo = Array [ 0 ] ;
for ( int i = 1 ; i < nu ; i++ )
   if ( Array [ i ] <= minimo )
     minimo = Array [ i ] ;
return minimo ;
}

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

EDITADO.

[y por lo menos 3.123.133 en lugar de probar más de 1 millón de factores, solo pruebas unos 884 factores y listo...]

entonces ejemplo, para saber si 211 (raíz ~14.5) es primo solo basta con probar 2, 3, 5, 7, 9, 11, 13 según tu algoritmo y solo probarías 7 factores en lugar de 211 dándole mucha velocidad...

y por lo menos 3.123.133 en lugar de probar más de 1 millón de factores, solo pruebas unos 884 factores y listo...

Eso último no está nada claro, si el número es 1 millón habría que probar según tu propuesta hasta num*num = 1000 000 , es decir de 3 a num=999 (1000).

Pero aún así se estaría trabajando en balde ya que probaríamos, entre otros, 15, 25, 27, 33, 35, 45, 49, ......que sería una redundancia ya que si  es divisible entre 3 y 5 el probar con 15 está de más y así sucesivamente.

Es decir, tan sólo hay que probar con divisores que, además de ser impares, sean primos, es decir:

3 , 5 , 7, 11 , 13 , 15 , 17 , 19 , 21 , 23 , 25 , 27  , 29 ,31 ,   33  ,   35 , 37 , 39 , 41 , 43 , 45 , 47 ,   49 ......

En el caso de 1000 000 hasta num = 1000 ( 1000*1000=1000000) hay en principio que tomar los impares, que son 500. Pero de ellos tan sólo hay 168 primos con lo que ya reducimos considerablemente el número de probaturas.

Y en el caso de 100 000 0000 hay ¡¡¡ "50 000 000" ¡¡¡ de impares pero tan solo 5 761 455 primos, con lo que ahorramos las pruebas en un factor de casi 20.

Por lo que de una forma simple se pueden ir guardando los primos obtenidos en un array, "primos", e ir probando sólo a estos en lugar de todos los impares, algo como:

Código (cpp) [Seleccionar] Expandir

 for ( primos[k] ; prims[k] * primos[k] <= n ; k++ ) {
     if ( n % primos[k] == 0 )

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