elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Usando Git para manipular el directorio de trabajo, el índice y commits (segunda parte)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  codigo para calcular los numeros primos
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: 1 [2] 3 4 Ir Abajo Respuesta Imprimir
Autor Tema: codigo para calcular los numeros primos  (Leído 16,305 veces)
ivancea96


Desconectado Desconectado

Mensajes: 3.412


ASMático


Ver Perfil WWW
Re: codigo para calcular los numeros primos
« Respuesta #10 en: 24 Diciembre 2013, 16:19 pm »

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


En línea

amchacon


Desconectado Desconectado

Mensajes: 1.211



Ver Perfil
Re: codigo para calcular los numeros primos
« Respuesta #11 en: 24 Diciembre 2013, 16:33 pm »

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


« Última modificación: 24 Diciembre 2013, 16:45 pm por amchacon » En línea

Por favor, no me manden MP con dudas. Usen el foro, gracias.

¡Visita mi programa estrella!

Rar File Missing: Esteganografía en un Rar
minari02

Desconectado Desconectado

Mensajes: 26


Ver Perfil
Re: codigo para calcular los numeros primos
« Respuesta #12 en: 24 Diciembre 2013, 23:47 pm »

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:
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
  1.    #include <stdio.h>
  2.  
  3.    int main()
  4.    {
  5.       int n,i,j;
  6.       printf("Introduce el numero por favor: ");
  7.       fflush (stdout);
  8.       scanf("%d",&n);
  9.       printf("%4d",1);//dejar una memoria reservada para introducir un numero de cuatro digitos y empezar a contar de 1//
  10.       for (i = 2;i <= n;i++){//empezar desde 2 hasta que i sea menor o igual que "n" (numero introducido) incrementar 1//
  11.           j = 2;
  12.           while (j <= i && i % j != 0)//mientras j sea 2 y sea menor que o igual a i que t no sera 2 por
  13.                                      //el incremento y que el resto de la divicion de entre "i" y "j" sea diferente a 0//
  14.               j++; //hacer incremento en j;
  15.           if (i == j){//si "i" es igual a "j" imprimir j
  16.               printf("%4d",j);
  17.               fflush (stdout);
  18.           }
  19.       }
  20.       return 0;
  21.    }
  22.  

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  :P
En línea

amchacon


Desconectado Desconectado

Mensajes: 1.211



Ver Perfil
Re: codigo para calcular los numeros primos
« Respuesta #13 en: 25 Diciembre 2013, 12:27 pm »

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:
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  :P
Ese código no es la criba de erástotenes  :silbar:
En línea

Por favor, no me manden MP con dudas. Usen el foro, gracias.

¡Visita mi programa estrella!

Rar File Missing: Esteganografía en un Rar
minari02

Desconectado Desconectado

Mensajes: 26


Ver Perfil
Re: codigo para calcular los numeros primos
« Respuesta #14 en: 25 Diciembre 2013, 20:35 pm »

jeje... si ya me he dado cuenta  :xD  :rolleyes:  ;D  :silbar:
En línea

leosansan


Desconectado Desconectado

Mensajes: 1.314


Ver Perfil
Re: codigo para calcular los numeros primos
« Respuesta #15 en: 27 Diciembre 2013, 21:25 pm »

jeje... si ya me he dado cuenta  :xD  :rolleyes:  ;D  :silbar:

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
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. int main ()
  5. {
  6.    int i, j, cont=1, n;
  7.    //printf ("Introduzca numero: ");
  8.    //scanf ("%d", &n);
  9.    n=1000000;
  10.    int *a;
  11.    a =  malloc (sizeof(int)*n);
  12.    for (i=3;i<=n;i+=2)
  13.        a[i]=i;
  14.    /*printf ("2  ");*/
  15.    for (i=3; i*i<=n;i+=2)
  16.        for (j=i;i*j<=n;j+=2)
  17.            a[i*j]=0;
  18.    for (i=3;i<n;i+=2)
  19.        if (a[i]!=0){
  20.            //printf ("%d  ",a[i]);
  21.            cont++;/**/
  22.        }
  23.    printf("\n total = %d",cont);
  24.    free (a);
  25.    return 0;
  26. }
  27.  

Sí. ya sé que están desactivados el scanf y el printf, pero quería compararlo con el de amchacon  :laugh: :laugh: 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  :laugh: :laugh: 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. :laugh: :laugh:


;-)  ;-) Felices Navidades y Próspero Año Nuevo.  ;-)  ;-)

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


« Última modificación: 28 Diciembre 2013, 20:50 pm por leosansan » En línea

ivancea96


Desconectado Desconectado

Mensajes: 3.412


ASMático


Ver Perfil WWW
Re: codigo para calcular los numeros primos
« Respuesta #16 en: 27 Diciembre 2013, 21:47 pm »

Man prueba con 10^12 :O
En línea

amchacon


Desconectado Desconectado

Mensajes: 1.211



Ver Perfil
Re: codigo para calcular los numeros primos
« Respuesta #17 en: 27 Diciembre 2013, 22:43 pm »

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
  1. #include <stdio.h>
  2.  
  3. int main ()
  4. {
  5.    int i, j, cont=1, n;
  6.    //printf ("Introduzca numero: ");
  7.    //scanf ("%d", &n);
  8.    n=1000000;
  9.    int *a;
  10.    a =  malloc (sizeof(int)*n);
  11.    for (i=3;i<=n;i+=2)
  12.        a[i]=i;
  13.    /*printf ("2  ");*/
  14.    for (i=3; i*i<=n;i+=2)
  15.        for (j=i;i*j<=n;j+=2)
  16.            a[i*j]=0;
  17.    for (i=3;i<n;i+=2)
  18.        if (a[i]!=0){
  19.            //printf ("%d  ",a[i]);
  20.            cont++;/**/
  21.        }
  22.    printf("\n total = %d",cont);
  23.    return 0;
  24. }
  25.  

Sí. ya sé que están desactivados el scanf y el printf, pero quería compararlo con el de amchacon  :laugh: :laugh: 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  :laugh: :laugh: 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  :silbar:
En línea

Por favor, no me manden MP con dudas. Usen el foro, gracias.

¡Visita mi programa estrella!

Rar File Missing: Esteganografía en un Rar
leosansan


Desconectado Desconectado

Mensajes: 1.314


Ver Perfil
Re: codigo para calcular los numeros primos
« Respuesta #18 en: 27 Diciembre 2013, 22:59 pm »

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

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! ..... !!!!
En línea

amchacon


Desconectado Desconectado

Mensajes: 1.211



Ver Perfil
Re: codigo para calcular los numeros primos
« Respuesta #19 en: 27 Diciembre 2013, 23:15 pm »

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
En línea

Por favor, no me manden MP con dudas. Usen el foro, gracias.

¡Visita mi programa estrella!

Rar File Missing: Esteganografía en un Rar
Páginas: 1 [2] 3 4 Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
[Python 2.6] Funcion generadora de Numeros primos (5.761.455 primos en 19 seg)
Scripting
katas 2 8,099 Último mensaje 10 Marzo 2010, 01:50 am
por Novlucker
Patrón para los números primos
Desafíos - Wargames
Jesusdpm 2 4,539 Último mensaje 30 Septiembre 2010, 21:50 pm
por MdosMil
calcular numeros primos « 1 2 »
Programación C/C++
AlkatraaZ 12 9,099 Último mensaje 4 Julio 2012, 20:19 pm
por AlkatraaZ
[JS] ¿Programa para calcular números primos?
Scripting
Linton 5 16,777 Último mensaje 23 Julio 2013, 07:40 am
por Linton
Ayuda con código para calcular los días de un mes
Programación C/C++
D_F4UL7 1 1,058 Último mensaje 25 Octubre 2016, 15:22 pm
por MAFUS
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines