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:
- Saltarse todos los pares en el
for
exterior. - Precomputar los primos bajo 10 millones para no tener que evaluar
sympy.isprime()
una y otra vez para el mismo valor. - 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