Skip to main content
1 de 4
Candid Moe
  • 26.6k
  • 10
  • 23
  • 47

Esto es lo que he logrado. Creo que hay espacio para mejorar.

import time
import sympy

preload_primes = 10_000_000
primes_set = {i for i in range(3, preload_primes, 2) if sympy.isprime(i)}
start = int(time.time())

n = 1_000_000
iteraciones = 0

for i in range(3, n, 2):
    primes = 0
    for j in range(1, i):
        iteraciones += 1

        k = j * j - j + i

        if k in primes_set or (k > preload_primes and sympy.isprime(k)):
            primes += 1
            #   ¿Cuantas iteraciones (y potenciales primos quedan)
            potential_primes = i - j
            #   Evaluar si podemos alcanzar tada > 0.5 en esta corrida
            if (primes + potential_primes) / (i - 1) <= 0.5:
                #   No quedan suficientes primos para alcanzar tada > 0.5.
                break
    tada = primes / (i - 1)
    if tada > 0.5:
        print(f"{i} {tada}")

end = int(time.time())
print(int(end-start), "s, ", iteraciones, "iteraciones")

Optimizaciones:

  1. Saltarse todos los pares en el for exterior.
  2. Precomputar los primos bajo 10 millones para no tener que evaluar sympy.isprime() una y otra vez para el mismo valor.
  3. Abandonar el for interior tan pronto quede claro que no llegamos al umbral requerido (tada > 0.5).

Probando con n = 10_000 y mi anciano tarro, obtengo estos resultados:

Tiempo : 12 segundos

Iteraciones: 14.725.596 iteraciones

3 1.0
5 1.0
7 0.6666666666666666
11 1.0
17 1.0
41 1.0
47 0.5652173913043478
59 0.5862068965517241
67 0.5454545454545454
101 0.68
107 0.6698113207547169
161 0.50625
221 0.5863636363636363
227 0.584070796460177
347 0.5057803468208093
377 0.5079787234042553
12 s,  14725596 iteraciones

Process finished with exit code 0
Candid Moe
  • 26.6k
  • 10
  • 23
  • 47