Título: Mejorar el codigo Publicado por: AprendiendoAProgramar en 19 Diciembre 2017, 23:45 pm Buenas.
Desarrolle un código para que me salieran los numeros primos de 1-100, aunque lo logré creo que mi código se puede mejorar mucho más para simplificarlo, ¿alguien podría ayudarme? Código
Título: Re: Mejorar el codigo Publicado por: engel lex en 20 Diciembre 2017, 01:23 am 2 detalles sobre los numeros primos
1- nunca un par es primo, si no evaluas pares te ahorras el 50% del proceso 2- el minimo multiplo de un numero nunca es mayor que su raíz, es decir, si desglosamos 100 Código: 1 2 4 5 10 el punto de confluencia siempre será su raiz, ya desde allí es la misma cuenta invertida, con esto et vas a ahorrar un monton de ciclos, por ejemplo para saber si 1.000.001 es primo solo es necesario probar hasta 1.000, así que son 1.000 ciclos (en este caso solo el 0.1% del trabajo y por ser raíz la eficiencia aumenta con lo grande del numero)... sin embargo calcular la raiz cuadrada es una operacion pesada y debemos velar que esto no consuma el proceso que nos ahorramos, así que lo calculamos en inversión... por esto antes de hacer un programa es importante investigar todas las teorías y temas asociados... estos 2 consejos son basicos... con esto para los primos de 1.000.001 solo necesitas 0.05% del trabajo que haría tu código si metemos allí los multiplos de 3 nos reducimos 15% más y el codigo queda algo como Código
lo hice de mente, espero no tenga errores Título: Re: Mejorar el codigo Publicado por: Serapis en 20 Diciembre 2017, 18:26 pm Yo no lo haría de forma ligeramente diferente a como lo resuelve engel lex
Básicamente sabemos que solo tiene posibilidades de ser primo si acaba en 1,3,7 ó 9, luego esa debería ser la primera condición a verificar. Luego, en efecto basta con llegar a la raíz cuadrada del número más alto, ya que a*b = b*a, con lo que al llegar al punto donde 'a' sea la raíz cuadrada, luego los valores de 'a', irán tomando los de 'b' y viceversa... Código: buleano = funcion EsPrimo(entero Valor) Aparte de eso, el bucle puede mejorarse toda vez que sabemos que si acaba en 5, no será primo, y también porque muchos impares son múltiplos de 3 (esto es cada 3 impares seguidos, 1 es múltiplo de 3): 11,13->15; 17,19->21; 23,25->27; 29,31->33 . Queda a tu esfuerzo optimizar dichos casos... Título: Re: Mejorar el codigo Publicado por: MAFUS en 20 Diciembre 2017, 20:14 pm Para aligerar aún más las cosas (a expensas de usar más memoria) te diría que fueras guardando los primos encontrados en una lista dinámica y usaras los elementos de esa lista como divisores del número que estás operando. Si llegas al final de ella ( o superas la raíz cuadrada del número), sin que ningún elemento haya sido divisible por el número, has encontrado el siguiente primo y lo incluyes en la cola de la lista. Así te evitas de realizar muchas operaciones.
La razón de esto es que cuando factorizas, si te das cuenta, usas siempre el menor primo. Título: Re: Mejorar el codigo Publicado por: CalgaryCorpus en 21 Diciembre 2017, 04:02 am Otra manera de optimizar esta logica es modificando el ciclo propuesto que parte en 7 y que va de 2 en 2, haciaendo que sume 4 y luego sume 2 (alternadamente), saltandose posibles factores que se sabe no son primos.
7, (+4=) 11, (+2=) 13, (+4=) 17, (+2=) 19, (+4=) 23, (+2=) 25, (+4=) 29, (+2=) 31, ... Título: Re: Mejorar el codigo Publicado por: engel lex en 21 Diciembre 2017, 05:13 am Otra manera de optimizar esta logica es modificando el ciclo propuesto que parte en 7 y que va de 2 en 2, haciaendo que sume 4 y luego sume 2 (alternadamente), saltandose posibles factores que se sabe no son primos. 7, (+4=) 11, (+2=) 13, (+4=) 17, (+2=) 19, (+4=) 23, (+2=) 25, (+4=) 29, (+2=) 31, ... justamente esto hago ;) de cabeza evalúa 2 y 3, de allí en más empieza en 5 y evalúa x y x+2, luego avanza 6 es decir va algo como 5;7, 11;13, 17;19, 23;25, 29;31, 37;43 |