<div dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote">2012/12/26 Daπid <span dir="ltr"><<a href="mailto:davidmenhur@gmail.com" target="_blank">davidmenhur@gmail.com</a>></span></div><div class="gmail_quote">
<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
Calculando todos los primos desde 2 hasta n tenemos (spoiler):<br>
<br>
<a href="http://pastebin.com/fMRH5xKK" target="_blank">http://pastebin.com/fMRH5xKK</a><br>
<br></blockquote><div><br></div><div style>Lo que hace este programa tiene un nombre: "la criba de Eratóstenes". Es muy simple en cuanto a su concepción y debe de ser uno de los métodos conceptuales más viejos para optimizar el cálculo de primos (al menos los documentados).</div>
<div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
Este programa tarda 0.3 s en calcular los primos hasta 15 000, y 13 s<br>
en encontrar los 13 843 primos menores que 150 000. Tu versión tarda<br>
unos 3 segundos para el primer caso.<br>
<br>
El proceso se puede encapsular más. Podemos echar mano de la<br>
programación funcional y hacer que isprime devuelva por defecto True,<br>
salvo cuando vea que el número es compuesto, en cuyo caso devolverá<br>
False.<br>
<br>
<a href="http://pastebin.com/gnFrcpYC" target="_blank">http://pastebin.com/gnFrcpYC</a><br>
<br>
Con esto, hemos reducido el tiempo de cálculo a la mitad.<br></blockquote><div><br></div><div style>Em... No sé de dónde sacas esa idea. El segundo listado es equivalente al primero, abstrayendo el test de primalidad en una función aparte. Como Python no soporta funciones "inline", esto introduce una llamada a función, con lo que, intuitivamente, debería ser ligeramente más lento. Y lo es: el mejor tiempo de ejecución (para primos hasta 15000) en mi máquina es de 125ms para tu primera propuesta y de unos 143ms para el segundo.</div>
<div style><br></div><div style>Ten en cuenta que lo único que estás ahorrando son unas pocas operaciones rápidas que se ejecutan en tiempo despreciable. Lo que más influye en el tiempo de ejecución son el bucle en sí y el append, que se ejecuta sólo para algo más del 11% de los números (de esos 15000).</div>
<div style><br></div><div style>De hecho, este otro listado, que es más compacto, se ejecuta en básicamente el mismo tiempo que el primer intento, aún descomponiéndose en menos instrucciones básicas:</div><div style><br></div>
<div style><a href="http://pastebin.com/vQ0eLPAZ">http://pastebin.com/vQ0eLPAZ</a><br></div><div style><br></div></div></div></div>