Skip to main content
Mejora calculo de primos potenciales por delante en la secuencia
Origen Enlace
Candid Moe
  • 26.6k
  • 10
  • 23
  • 47
import time
import sympy

def gensec(n: int, factores: list[int]):
    #   Función generadora que retorna la secuencia 1 a n
    #   excluyendo los múltiplos de los enteros de la
    #   lista de factores.
    indices = factores.copy()
    num_ind = len(indices)
    for valor in range(1, n):
        if valor in indices:
            #   Valor es múltiplo de alguno de los factores;
            #   descartarlo
            for i in range(num_ind):
                #   Avanzar los indices para que todos sean
                #   mayores que 'valor'.
                if indices[i] == valor:
                    indices[i] += factores[i]
        else:
            yield valor

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 = 10_000
iteraciones = 0

for i in range(3, n, 2):
    #   Determinar los factores primos de i
    factores = sympy.primefactors(i)
    primes = 0
    #   Recorrer los enteros de 1 a i saltando todos
    #   los múltiplos de los factores primos de i.
    for j in gensec(i, factores):
        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 + 1) // 2 # Descontar los pares
            #   Evaluar si podemos alcanzar tada > 0.5 en esta corrida
            if (primes + potential_primes) <= 0.5 * (i - 1):
                #   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")

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

Mejoras pendientes En el cálculo de potential_primes hay que descontar todos los múltiplos de los factores primos en factores. Por el momento, sólo descuento los valores pares.

Tiempo : 12 segundos< 1 segundo

Iteraciones: 12.09280.559397 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
120 s,  1209255980397 iteraciones    

Process finished with exit code 0
import time
import sympy

def gensec(n: int, factores: list[int]):
    #   Función generadora que retorna la secuencia 1 a n
    #   excluyendo los múltiplos de los enteros de la
    #   lista de factores.
    indices = factores.copy()
    num_ind = len(indices)
    for valor in range(1, n):
        if valor in indices:
            #   Valor es múltiplo de alguno de los factores;
            #   descartarlo
            for i in range(num_ind):
                #   Avanzar los indices para que todos sean
                #   mayores que 'valor'.
                if indices[i] == valor:
                    indices[i] += factores[i]
        else:
            yield valor

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 = 10_000
iteraciones = 0

for i in range(3, n, 2):
    #   Determinar los factores primos de i
    factores = sympy.primefactors(i)
    primes = 0
    #   Recorrer los enteros de 1 a i saltando todos
    #   los múltiplos de los factores primos de i.
    for j in gensec(i, factores):
        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) <= 0.5 * (i - 1):
                #   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")

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

Tiempo : 12 segundos

Iteraciones: 12.092.559 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,  12092559 iteraciones    

Process finished with exit code 0
import time
import sympy

def gensec(n: int, factores: list[int]):
    #   Función generadora que retorna la secuencia 1 a n
    #   excluyendo los múltiplos de los enteros de la
    #   lista de factores.
    indices = factores.copy()
    num_ind = len(indices)
    for valor in range(1, n):
        if valor in indices:
            #   Valor es múltiplo de alguno de los factores;
            #   descartarlo
            for i in range(num_ind):
                #   Avanzar los indices para que todos sean
                #   mayores que 'valor'.
                if indices[i] == valor:
                    indices[i] += factores[i]
        else:
            yield valor

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 = 10_000
iteraciones = 0

for i in range(3, n, 2):
    #   Determinar los factores primos de i
    factores = sympy.primefactors(i)
    primes = 0
    #   Recorrer los enteros de 1 a i saltando todos
    #   los múltiplos de los factores primos de i.
    for j in gensec(i, factores):
        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 + 1) // 2 # Descontar los pares
            #   Evaluar si podemos alcanzar tada > 0.5 en esta corrida
            if (primes + potential_primes) <= 0.5 * (i - 1):
                #   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")

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

Mejoras pendientes En el cálculo de potential_primes hay que descontar todos los múltiplos de los factores primos en factores. Por el momento, sólo descuento los valores pares.

Tiempo : < 1 segundo

Iteraciones: 80.397 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
0 s,  80397 iteraciones    

Process finished with exit code 0
se añadieron 153 caracteres en el cuerpo
Origen Enlace
Candid Moe
  • 26.6k
  • 10
  • 23
  • 47
  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). Este chequeo puede hacerse para cada iteración del for interno; aunque reduce ligeramente el número de iteraciones, incrementa el tiempo de ejecución.
  4. En lugar de range(1, i) en el for interno, uso una función generadora gensec(i, factores) para saltar valores con factores primos comunes a 'i'.
  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).
  4. En lugar de range(1, i) en el for interno, uso una función generadora gensec(i, factores) para saltar valores con factores primos comunes a 'i'.
  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). Este chequeo puede hacerse para cada iteración del for interno; aunque reduce ligeramente el número de iteraciones, incrementa el tiempo de ejecución.
  4. En lugar de range(1, i) en el for interno, uso una función generadora gensec(i, factores) para saltar valores con factores primos comunes a 'i'.
Agrega función generadora para reducir el número de iteraciones
Origen Enlace
Candid Moe
  • 26.6k
  • 10
  • 23
  • 47
import time
import sympy

def gensec(n: int, factores: list[int]):
    #   Función generadora que retorna la secuencia 1 a n
    #   excluyendo los múltiplos de los enteros de la
    #   lista de factores.
    indices = factores.copy()
    num_ind = len(indices)
    for valor in range(1, n):
        if valor in indices:
            #   Valor es múltiplo de alguno de los factores;
            #   descartarlo
            for i in range(num_ind):
                #   Avanzar los indices para que todos sean
                #   mayores que 'valor'.
                if indices[i] == valor:
                    indices[i] += factores[i]
        else:
            yield valor

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_00010_000
iteraciones = 0

for i in range(3, n, 2):
    #   Determinar los factores primos de i
    factores = sympy.primefactors(i)
    primes = 0
    #   Recorrer los enteros de 1 a i saltando todos
    #   los múltiplos de los factores primos de i.
    for j in rangegensec(1i, ifactores):
        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) /<= 0.5 * (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")
  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).
  4. En lugar de range(1, i) en el for interno, uso una función generadora gensec(i, factores) para saltar valores con factores primos comunes a 'i'.

La función generadora recibe la lista de factores primos de i. Al iterar, la función descarta todos los valores que sean múltiplos de algun factor, pues en ese caso, la expresión

k = j * j - j + i  

es divisible por al menos un factor primo, por lo que k no es primo.

Iteraciones: 1412.725092.596559 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,  1472559612092559 iteraciones    

Process finished with exit code 0
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")
  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).

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
import time
import sympy

def gensec(n: int, factores: list[int]):
    #   Función generadora que retorna la secuencia 1 a n
    #   excluyendo los múltiplos de los enteros de la
    #   lista de factores.
    indices = factores.copy()
    num_ind = len(indices)
    for valor in range(1, n):
        if valor in indices:
            #   Valor es múltiplo de alguno de los factores;
            #   descartarlo
            for i in range(num_ind):
                #   Avanzar los indices para que todos sean
                #   mayores que 'valor'.
                if indices[i] == valor:
                    indices[i] += factores[i]
        else:
            yield valor

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 = 10_000
iteraciones = 0

for i in range(3, n, 2):
    #   Determinar los factores primos de i
    factores = sympy.primefactors(i)
    primes = 0
    #   Recorrer los enteros de 1 a i saltando todos
    #   los múltiplos de los factores primos de i.
    for j in gensec(i, factores):
        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) <= 0.5 * (i - 1):
                #   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")
  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).
  4. En lugar de range(1, i) en el for interno, uso una función generadora gensec(i, factores) para saltar valores con factores primos comunes a 'i'.

La función generadora recibe la lista de factores primos de i. Al iterar, la función descarta todos los valores que sean múltiplos de algun factor, pues en ese caso, la expresión

k = j * j - j + i  

es divisible por al menos un factor primo, por lo que k no es primo.

Iteraciones: 12.092.559 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,  12092559 iteraciones    

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