codigo para calcular los numeros primos

[ivancea96]

El problema de eso, yo se lo veo cuando tratámos números grandes. Véase 10^9.

[amchacon]

El problema de eso, yo se lo veo cuando tratámos números grandes. Véase 10^9.

¿Que problema hay con eso? El bucle hace raiz(n) iteraciones (es decir, es muy eficiente). En el caso que tu propones haría 10^3 iteraciones.

Cualquier cpu puede hacer 1000 iteraciones de un bucle en una soplada:
http://imageshack.us/a/img542/3319/0133.png

Si te refieres a generar la tabla completa (y no al calculo directo). Su complejidad es n*log n (más lento, pero también es eficiente). A mi me tarda poco (tardo unos 2 segundos en generar la tabla con todos los primos a 10 ^ 9).

[minari02]

Hola, que tal?

Muchas gracias por sus respuestas y creo que el mas simplificado es de amchacon he puesto su codigo y funciona perfecto aunque lo que no entiendo es como rayos funciono sin incluir la libreria y sin poner el

Código [Seleccionar] Expandir

int main bien ya antes habia encontrado un codigo funcional, el cual ya he mostrado a leosansan y me ha hecho las correciones necesarias y pues aqui lo posteo:

Código (csharp) [Seleccionar] Expandir

    #include <stdio.h>

    int main()
    {
       int n,i,j;
       printf("Introduce el numero por favor: ");
       fflush (stdout);
       scanf("%d",&n);
       printf("%4d",1);//dejar una memoria reservada para introducir un numero de cuatro digitos y empezar a contar de 1//
       for (i = 2;i <= n;i++){//empezar desde 2 hasta que i sea menor o igual que "n" (numero introducido) incrementar 1//
           j = 2;
           while (j <= i && i % j != 0)//mientras j sea 2 y sea menor que o igual a i que t no sera 2 por
                                      //el incremento y que el resto de la divicion de entre "i" y "j" sea diferente a 0//
               j++; //hacer incremento en j;
           if (i == j){//si "i" es igual a "j" imprimir j
               printf("%4d",j);
               fflush (stdout);
           }
       }
       return 0;
    }


Ok.. los comentarios los he puesto yo, si hay error avísenme, por cierto que aqui se usa claramente el algoritmo La criba de Eratóstenes.

no digo que sea mejor, si no que la forma mas basica y entendible. supongo que la mejor seria la de  amchacon  que piensan?

saludos 

[amchacon]

Hola, que tal?

Muchas gracias por sus respuestas y creo que el mas simplificado es de amchacon he puesto su codigo y funciona perfecto aunque lo que no entiendo es como rayos funciono sin incluir la libreria y sin poner el

Código [Seleccionar] Expandir

int main

¿Ein?

Está el int main y el #include <stdio.h>. Vuelvetelo a mirar que además lo tuve que editar para mejorar su eficiencia.

Ok.. los comentarios los he puesto yo, si hay error avísenme, por cierto que aqui se usa claramente el algoritmo La criba de Eratóstenes.

no digo que sea mejor, si no que la forma mas basica y entendible. supongo que la mejor seria la de  amchacon  que piensan?

saludos 

Ese código no es la criba de erástotenes 

[minari02]

jeje... si ya me he dado cuenta       

[leosansan]

jeje... si ya me he dado cuenta        

Perdona que había quedado en contestar, pero esto de las Fiestas me ocupan familiarmente demasiado.

No quería dejar pasar mi versión de la criba de Eratóstenes, para que no se diga que no ayudamos:

Código (cpp) [Seleccionar] Expandir


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

int main ()
{
   int i, j, cont=1, n;
   //printf ("Introduzca numero: ");
   //scanf ("%d", &n);
   n=1000000;
   int *a;
   a =  malloc (sizeof(int)*n);
   for (i=3;i<=n;i+=2)
       a[i]=i;
   /*printf ("2  ");*/
   for (i=3; i*i<=n;i+=2)
       for (j=i;i*j<=n;j+=2)
           a[i*j]=0;
   for (i=3;i<n;i+=2)
       if (a[i]!=0){
           //printf ("%d  ",a[i]);
           cont++;/**/
       }
   printf("\n total = %d",cont);
   free (a);
   return 0;
}


Sí. ya sé que están desactivados el scanf y el printf, pero quería compararlo con el de amchacon   Y esto son los resultados, desactivando también los printf en el de amchacon y dejando en ambos casos activo solamente el contador final de primos resultantes:

No es por nada   pero parece que el mío va de un 25 a un 33 por ciento más rápido, y eso que solamente he podido usar 10^6, cuando en realidad quería meterle más caña, pero ...... en el mío no tengo problema en tomar 10^8, pero el de amchacon se cuelga en mi ordenador desde 10^7. Supongo que es problema mío, y de tener declarada la matriz en el caso de amchacon como int[]. Es un fastidio porque, como ejemplo, no puedo usar en mi ordenata matrices de 1000x1000. ¡SNIFFF!. ¿Os pasa algo parecido a vosotros o podéis manejar rangos superiores a 10^8 o matrices de orden superior a 1000?.

¡OJO!, que los comentarios son en tono jocoso y festivos, que es lo que se lleva por estas fechas.   Nada de piques, ¿vale?.
EN realidad amigo amchacon, tu código me parece una virguería, demuestras unos amplios conocimientos incluso en algo tan simple como el ejemplo que nos ocupa. Espero por lo menos llegar a aproximarme con el tiempo .... y una caña para que sea más llevadero.

  Felices Navidades y Próspero Año Nuevo.    

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

[ivancea96]

Man prueba con 10^12 :O

[amchacon]

Perdona que había quedado en contestar, pero esto de las Fiestas me ocupan familiarmente demasiado.

No quería dejar pasar mi versión de la criba de Eratóstenes, para que no se diga que no ayudamos:

Código (cpp) [Seleccionar] Expandir


#include <stdio.h>

int main ()
{
   int i, j, cont=1, n;
   //printf ("Introduzca numero: ");
   //scanf ("%d", &n);
   n=1000000;
   int *a;
   a =  malloc (sizeof(int)*n);
   for (i=3;i<=n;i+=2)
       a[i]=i;
   /*printf ("2  ");*/
   for (i=3; i*i<=n;i+=2)
       for (j=i;i*j<=n;j+=2)
           a[i*j]=0;
   for (i=3;i<n;i+=2)
       if (a[i]!=0){
           //printf ("%d  ",a[i]);
           cont++;/**/
       }
   printf("\n total = %d",cont);
   return 0;
}


Sí. ya sé que están desactivados el scanf y el printf, pero quería compararlo con el de amchacon   Y esto son los resultados, desactivando también los printf en el de amchacon y dejando en ambos casos activo solamente el contador final de primos resultantes:

No es por nada   pero parece que el mío va de un 25 a un 33 por ciento más rápido, y eso que solamente he podido usar 10^6, cuando en realidad quería meterle más caña,

Los tiempos son muy cortos para suponer eso, ahí puede influir muchos factores externos.

Pero aún así es más eficiente, entre otras cosas porque no tienes llamadas a función y esas cosas. El algoritmo es el mismo básicamente.

pero ...... en el mío no tengo problema en tomar 10^8, pero el de amchacon se cuelga en mi ordenador desde 10^7. Supongo que es problema mío, y de tener declarada la matriz en el caso de amchacon como int[]. Es un fastidio porque, como ejemplo, no puedo usar en mi ordenata matrices de 1000x1000. ¡SNIFFF!. ¿Os pasa algo parecido a vosotros o podéis manejar rangos superiores a 10^8 o matrices de orden superior a 1000?.

El problema esque yo meto los datos en la pila y tú usas memoria dinámica (malloc).

Tienes la explicación detallada aquí (segundo mensaje):
http://foro.elhacker.net/programacion_cc/duda_memoria_dinamica_en_c-t391783.0.html

Man prueba con 10^12 :O

Te sales del rango de los enteros  

[leosansan]

.......................................................................................

Pero aún así es más eficiente, entre otras cosas porque no tienes llamadas a función y esas cosas. El algoritmo es el mismo básicamente.
.......................................

Supongo que también influye el hecho de que yo empiezo en 3 y voy de dos en dos, obviando de esa forma las operaciones con los pares, que no son primos ni son pocos. Lo que más me ha gustado es la concisión en el código

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

[amchacon]

Supongo que también influye el hecho de que yo empiezo en 3 y voy de dos en dos, obviando de esa forma las operaciones con los pares, que no son primos ni son pocos. Lo que más me ha gustado es la concisión en el código

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

Ah pues no había pensado en eso. Quizás eso haya sido lo más decisivo xD