Referencia: Este pregunta está inspirada en el [código publicado][1] por Matt Parker en el canal Numberphile de YT, en un video llamado *Caboose Numbers*.

[![introducir la descripción de la imagen aquí][2]][2]

La secuencia entera

    n ** 2 - n + C, para n=1, 2, ... C - 1

produce números primos para 6 valores de C (2, 3, 5, 11, 17 y 41). Para otros valores de C, la secuencia produce una combinación de primos y valores compuestos. 

El objetivo del código es probar todos los valores C entre 1 y 1.000.000.000 para identificar aquellos que producen secuencias con más primos que compuestos (`if tada > 0.5:`).

He transcrito el código publicado eliminando las grabaciones de los resultados, para simplificarlo:

    import sympy

    n = 1_000_000_000
    
    for i in [i for i in range(1, 3)]:
        values = [j**2 - j + i for j in range(1,i)]
        primes = 0
        for k in values:
            if sympy.isprime(k):
                primes += 1
        tada = primes/len(values)
        if tada > 0.5:
            print(f"{i} {tada}")

Hay dos tipos de optimización posible. La primera es de tipo "aritmética". Por ejemplo, dado que la expresión se puede reescribir como

    n * (n - 1) + C

está claro que `n * (n - 1)` siempre será par, pues al menos uno de los factores es par. En consecuencia, cuando C es par, la expresión producirá sólo valores pares, sin ningún valor primo. Puedo optimizar cambiando el `for` externo para saltarme los valores de C pares. Así se reduce a la mitad el número de iteraciones.

El segundo tipo de optimización, que busco aquí, es de implementación en Python. Por ejemplo, el `for` más externo se puede sustituir por

    for i in range(3, n):

con lo que se evita generar y procesar una lista de 1.000 millones de elementos en RAM.

O, mejor, puede escribir

    for i in range(3, n, 2):

para evitar los valores pares.

La pregunta es: ¿Qué cambios puedo hacer en la implementación para optimizar su tiempo de ejecución? Por ejemplo, podría usar valores precomputados en alguna lista, set o diccionario para no tener que repetir la consulta `sympy.isprime(k)` un millón de veces para un mismo valor de `k`.


  [1]: https://youtu.be/gM5uNcgn2NQ?t=433
  [2]: https://i.sstatic.net/Ge0BHxQE.png