¿Alguien me puede enseñar cómo optimizar aún más esta secuencia de comandos 'imprima hasta el enésimo número primo'?

Question

Tengo 17 años y comienzo a programar con la ayuda del lenguaje de programación Python.

He estado tratando de optimizar este algoritmo, quizás eliminando uno de los bucles, o con una prueba mejor para verificar los números primos.

Intentando calcular y mostrar 100000 números primos tiene la secuencia de comandos haciendo una pausa de unos 6 segundos, ya que rellena la lista con números primos antes de que la lista de primos se devuelva a la consola como salida.

He estado experimentando con el uso de

print odd, 

simplemente imprimir cada número primo encontrado, que es más rápido para las entradas más pequeñas como n = 1000, pero para n = 1000000 imprime la lista en sí mucho más rápido (tanto en el shell de python y en la consola).

Quizás todo el código/algoritmo se debe renovar, pero el script debe seguir siendo esencialmente el mismo: el usuario ingresa el número de números primos a imprimir (n) y el script devuelve todos los números primos hasta el enésimo primo número.

from time import time 
odd = 1 
primes = [2] 
n = input("Number of prime numbers to print: ") 
clock = time() 
def isPrime(number): 
    global primes 
    for i in primes: 
     if i*i > number: 
      return True 
     if number%i is 0: 
      return False 
while len(primes) < n: 
    odd += 2 
    if isPrime(odd): 
     primes += [odd] 
print primes 
clock -= time() 
print "\n", -clock 
raw_input() 

Me posible que desee volver a escribir toda la secuencia de comandos para utilizar un tamiz como el tamiz de Atkin: http://en.wikipedia.org/wiki/Sieve_of_Atkin

Sin embargo, yo soy simplemente un principiante en Python (o incluso en la programación: Empecé a escribir sólo el 2 Código semanas atrás) y sería todo un desafío para mí descubrir cómo codificar un algoritmo de Sieve of Atkin en Python.

deseo un hacker google a cabo no habría asimiento de la mano conmigo a través de este tipo de cosas :(

Answer 1

Una optimizaciones simples que podrían aplicarse sin hackear el código completo.

• el i * i en cada Primer obtiene un gran desperdicio ya que la lista se hace más largo. En lugar calcular la raíz cuadrada de i fuera del bucle y la prueba contra este valor dentro del bucle.

Cómo Alguna vez la raíz cuadrada es en sí misma un cálculo costoso y la mayoría de los números candidatos serán rechazados como divisibles por uno de los números primos inferiores (3,5,7), por lo que resulta que no es una buena optimización (¿pesimismo?). Pero no necesitamos ser tan precisos y una simple comprobación de que el primo es menos de un tercio del valor tiene un efecto similar sin el costo computacional del cálculo de la raíz cuadrada, pero a expensas de un número relativamente pequeño de datos innecesarios prueba.

Answer 2

Usted podría utilizar prime sieve, y con un simple giro:

1. Definir el primer primer 2 como lo hace, establecer el número más grande alcanzado (max) a 2;
2. Genera una lista de n números consecutivos desde max+1 hasta max+n;
3. Use el tamiz con los primos en esta lista. Al tamizar, establezca el número inicial de cada primo en el número más pequeño de la lista que podría dividirse por el primo;
4. Si la cantidad no es reacher, vaya a 2.

De esta manera, podría controlar la longitud de la lista y, a medida que la longitud aumente, la velocidad será más rápida. Sin embargo, esto es una reelaboración total del algoritmo, y es más difícil de programar.

Aquí hay un código de ejemplo, que es bastante crudo, pero esto sólo lleva tiempo inferior al 70% del original:

from math import sqrt 
from time import time 
primes = [2] 
max = 3 
n = input("Number of prime numbers to print: ") 
r=2 
clock = time() 
def sieve(r): 
    global primes 
    global max 
    s = set(range(max,max+r)) 
    for i in primes: 
     b=max//i 
     if (b*i<max): 
      b=b+1 
     b=b*i 
     while b<=max+r-1: 
      if b in s: 
       s.remove(b) 
      b=b+i 
    for i in s: 
     primes.append(i) 
while len(primes) < n: 
    r=primes[-1] 
    sieve(r) 
    max=max+r 
primes=primes[0:n] 
print primes 
clock -= time() 
print "\n", -clock 
raw_input() 

Hay muchas maneras de mejorar esto, esto sólo demuestra la noción del enfoque .

Además, esto puede hacer estallar la memoria cuando el número es grande. Utilicé el límite dinámico, intento de alguna manera aliviar esto.

Y si eres realmente curioso (y audaz), podrías mirar las implementaciones más complicadas en varios proyectos de código abierto. Un ejemplo es Pari/GP, que está escrito en C++, y es increíblemente rápido (Probé de 1 a 50000000 en menos de 1 minuto, si no recuerdo mal). Traducirlas a Python puede ser difícil, pero será útil, quizás no solo para usted ;-)

Answer 3

Cualquier número que termine en 5, que no sea 5, no es primo. Así que puede poner una declaración que omita cualquier número que termine en 5 que sea mayor que 5.

Answer 4

Como ya lo dijo Ziyao Wei, también probaría una implementación de Sieve. Lo único que mejoraría es usar el Prime number theorem como punto de partida para el tamaño utilizado.

Calcular la función inversa no es sencillo en python puro, pero un enfoque iterativo debería ser lo suficientemente bueno y de esa manera se podría obtener una idea bastante buena de lo grande que debería ser el tamiz. Como realmente no recuerdo las pruebas para el teorema en detalle y son las 6 de la mañana aquí, alguien más tendrá que intervenir para decir si el teorema garantiza algún límite superior que podría usarse para permitir el uso del simple colador sin tener que preocuparse de crecerlo. iirc que lamentablemente no es el caso.

Answer 5

Como ya se mencionó, el algoritmo presentado no se puede mejorar significativamente. Si se solicita una solución rápida, entonces el tamiz Eratosthenes es apropiado. El tamaño x del tamiz puede ser estimated usando n >= x/(ln x + 2) si x >= 55. Esta ecuación se puede resolver usando la iteración de Newton. El algoritmo presentado es aproximadamente 10 veces más rápido que el original:

def sieveSize(n): 
    # computes x such that pi(x) >= n (assumes x >= 55) 
    x = 1.5 * n # start 
    y = x - n * math.log(x) - 2 * n 
    while abs(y) > 0.1: 
     derivative = 1 - n/x 
     x = x - y/derivative 
     y = x - n * math.log(x) - 2 * n 
    return int(x) + 1 

def eratosthenes(n): 
    # create a string flags: flags[i]=='1' iff i prime 
    size = sieveSize(n) 
    flags = ['1'] * size # start with: all numbers are prime 
    flags[0] = flags[1] = '0' # 0 and 1 are not primes 
    i = 0 
    while i * i < size: 
     if flags[i] == '1': 
      for j in range(i * i, size, i): 
       flags[j] = '0' 
     i += 1 
    return flags 

def primes(n): 
    flags = eratosthenes(n) 
    prims = [] 
    for i in range(0, len(flags)): 
     if flags[i] == '1': 
      prims.append(i) 
    return prims 

prims = primes(100000)