 Autor
|
Tema: codigo para calcular los numeros primos (Leído 23,325 veces)
|
ivancea96
 Desconectado
Mensajes: 3.412
ASMático
|
El problema de eso, yo se lo veo cuando tratámos números grandes. Véase 10^9.
|
|
|
|
|
En línea
|
|
|
|
amchacon
Desconectado
Mensajes: 1.211
|
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.pngSi 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
|
|
|
|
minari02
Desconectado
Mensajes: 26
|
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 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: #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  |
|
|
|
|
En línea
|
|
|
|
amchacon
Desconectado
Mensajes: 1.211
|
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 ¿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 
|
|
|
|
|
En línea
|
|
|
|
minari02
Desconectado
Mensajes: 26
|
|
|
|
|
|
En línea
|
|
|
|
leosansan
Desconectado
Mensajes: 1.314
|
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:#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: 
¡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. ¡¡¡¡ Saluditos! ..... !!!!
|
|
|
|
« Última modificación: 28 Diciembre 2013, 20:50 pm por leosansan »
|
En línea
|
|
|
|
ivancea96
Desconectado
Mensajes: 3.412
ASMático
|
Man prueba con 10^12 :O
|
|
|
|
|
En línea
|
|
|
|
amchacon
Desconectado
Mensajes: 1.211
|
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:#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.htmlMan prueba con 10^12 :O
Te sales del rango de los enteros
|
|
|
|
|
En línea
|
|
|
|
leosansan
Desconectado
Mensajes: 1.314
|
.......................................................................................
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
Mensajes: 1.211
|
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
|
|
|
|
|
| Mensajes similares |
|
Asunto |
Iniciado por |
Respuestas |
Vistas |
Último mensaje |
|
|
[Python 2.6] Funcion generadora de Numeros primos (5.761.455 primos en 19 seg)
Python
|
katas
|
2
|
9,897
|
10 Marzo 2010, 01:50 am
por Novlucker
|
|
|
|
Patrón para los números primos
Desafíos - Wargames
|
Jesusdpm
|
2
|
5,959
|
30 Septiembre 2010, 21:50 pm
por MdosMil
|
|
|
|
calcular numeros primos
« 1 2 »
Programación C/C++
|
AlkatraaZ
|
12
|
12,247
|
4 Julio 2012, 20:19 pm
por AlkatraaZ
|
|
|
[JS] ¿Programa para calcular números primos?
Scripting
|
Linton
|
5
|
19,439
|
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
|
2,331
|
25 Octubre 2016, 15:22 pm
por MAFUS
|
 |
