[mperdi]

Hola, tengo que hacer un programa en Python que devuelva la lista de los números primos de Mersenne menores que limit. La función se llama mersenne_primos(limit).
La tengo hecha pero para límites muy grandes tarda mucho en calcularlo. A ver si a alguno se le ocurre como puedo mejorarlo.

Código: [Seleccionar]

def mersenne_primes(limit):
primos = []
               for num in range(1, limit+1):
                   if esprimo(num):
                      mersenne = (2**num)-1
                      print (mersenne)
                      primos.append(mersenne)
               return primos

[geómetracat]

Lo que calculas ahí no son primos de Mersenne sino números de Mersenne. Es decir, tu programa te saca números de la forma \( 2^p - 1 \), con \( p \) primo, pero no necesariamente tienes que \( 2^p - 1 \) es un número primo. Se llaman primos de Mersenne a los números primos de la forma \( 2^p - 1 \) para algún número primo \( p \).

Al margen de esto, imagino que el cuello de botella en tu programa es la comprobación de si un número es primo o no. Para ello habría que saber como implementas la función \( esprimo \).
También me parece un poco raro que pidas al programa que vaya imprimiendo cada número que saca y además lo metas en una lista. Parece más natural imprimir la lista al final, o bien no meter los números en ninguna lista, si lo que quieres es solamente verlos por pantalla.

[feriva]

Hola, mperdi.

Dejando aparte lo que te dice geómetracat y  otras cosas más sobre el programa; ¿puedes usar módulos o no te dejan?

Da la sensación de que ahí has puesto un resumen-traducción del verdadero código, porque eso no funcionará, al menos sin módulos y laguna definición de variable.

Yo, por ejemplo, uso el módulo sympy, que tiene la función, entre otras, “isprime” (en otro caso habría que hacer una rutina para seleccionar primos, como puede ser la de la criba de Eratóstenes, que en Python es muy corta usando la función set)

Con Sympy se podría hacer muy simple:

Aunque no todos los Mersenne con “n” primo son primos, eso se puede aprovechar para hacer una selección previa; un código puede ser así:

Código: [Seleccionar]

from sympy import *

for n in range (1000):

if isprime (n):

k = (2**n-1)


if isprime (k):

print (n)

Le he mandado imprimir las potencias “n” de los que son primos, porque los Mersenne son muy largos.

También he puesto un rango no muy extenso para “n”; tarda mucho, claro, si tardara poco habría más Mersenne descubiertos; hasta ahora sólo se conocen éstos:

https://es.wikipedia.org/wiki/N%C3%BAmero_primo_de_Mersenne

Saludos.

[mperdi]

Creo que no me expliqué bien, mi código funciona e imprime la lista de números menores que el limit que tú introduces. El problema es que al probar la función en el terminal si le metes un limit muy alto tarda mucho en sacarte la lista y tengo que conseguir que no tarde tanto.
No puedo utilizar módulos es todo a base de funciones. Por ello me he creado una función donde te dice si un número es primo o no.

Código: [Seleccionar]

def esprimo(n):
    if n < 1:
        return False
    elif n == 2:
        return True
    else:
        for i in range(2, n):
            if n % i == 0:
                return False
        return True
   
   
def mersenne_primes(limit):
    primos = []
    for num in range(1, limit + 1):
        if esprimo(num):
            mersenne = (2**num) - 1
            if mersenne < limit:
                primos.append(mersenne)
    return primos

[mperdi]

Acabo de modificar la función y ha mejorado, pero me pone que el problema está en la función 'es primo', que hay un fallo en el bucle for i in range(2,n).

Código: [Seleccionar]

def esprimo(n):
    if n < 1:
        return False
    elif n == 2:
        return True
    else:
        for i in range(2, n):
            if n % i == 0:
                return False
        return True
def mersenne_primes(limit):
    primos = []
    i = 0
    while (2**i - 1 < limit):
        if esprimo(2**i - 1) == True:
            primos.append(2**i - 1)
        i = i + 1
    return primos

[feriva]

Creo que no me explique bien, mi código funciona e imprime la lista de números menores que el limit que tu introduces. El problema es que al probar la función en el terminal si le metes un limit muy alto tarda mucho en sacarte la lista y tengo que conseguir que no tarde tanto.
No puedo utilizar módulos es todo a base de funciones. Por ello me he creado una función donde te dice si un número es primo o no.

Ah, bien. No obstante, tienes que tener en cuenta eso que te decía geómetracat, no todos los \( 2**p-1 \) con p primo son primos, por tanto, no todos los \( 2**p-1 \) son primos de Mersenne.

La función que has hecho es ineficiente, es verdad.

Una de las cosas más básicas para comprobar la primalidad de un número es fijarse en esto; te lo explico con un ejemplo para que veas el funcionamiento:

1,2,3,4,5,6,7,8,9,10,12,13,14,15, 16, 17

Los no primos que hay hasta 17 (por tomar un número cualquiera) no pueden ser mayores que \( 4*4 \), por tanto, todos los compuestos serán múltiplos de algún primo menor que 4 (5*5, por ejemplo, es un compuesto que no cabe ahí, es mayor). Es decir, 3*5 ó 2*7... sí tiene un primo mayor que 4, pero la cuestión es que no dejan de tener como factor un primo más pequeño, el 3; todo los compuestos tiene alguno de estos factores 2 ó 3 con toda seguridad.

Así pues, si tú vas a comprobar si un “n” es primo, basta que tomes los números desde la parte entera de la raíz cuadrada de “n” hacia abajo, hacia 1, y dividas a “n” por éstos y compruebes el resto con la función %. Así ahorrarás bastante.

No obstante, el Python tiene funciones estándar (sin usar módulo) muy útiles que pueden agilizar esto, como la función set que te decía; pero tampoco sé si te permiten usar cualquier función aunque sea estándar. Si puedes usar cualquiera, me lo dices e intento hacer un programa; a ver si no tarda mucho.

Saludos.

[feriva]

Más de 8, con programación de andar por casa y en un tiempo digamos instantáneo, no me salen, lo he intentado pero no. Tiene que ser implementando el algoritmo de Lucas-Lehmer; un amigo que pasaba por el foro hizo varios programas para estos primos, hay hilos enteros hablando de ellos, pero no creo que te pidan programar el test de Lucas-Lehmer. No obstante, te lo he buscado y si tienes curiosidad lo puedes ver aquí:

https://stackoverflow.com/questions/45195059/efficient-mersenne-prime-generator-in-python

Éste puede ser un código (yo no programo “académicamente”, pero supongo que podrás traducirlo).

Código: [Seleccionar]


limite=50

def P_Mersenne (n):

bandera2=1

mersenne = 2**n-1

rr= int (mersenne**(0.5))

for s in range (2,rr+1):

if mersenne % s ==0:

bandera2=0

return
if bandera2 ==1:

print (mersenne)


# Bucle anidado para ir listando los primos

for n in range (2,limite):

bandera = 1

r = int (n**(0.5))

for k in range (2,r+1):

if n % k ==0:

bandera=0

break

if bandera ==1:

P_Mersenne(n) # Llamada a la funcion




Lo he puesto para que sólo saque los que salen de golpe en pantalla, éstos:

3
7
31
127
8191
131071
524287
2147483647

Lo que llamo bandera lo que en código máquina o ensamblador se conoce como lo mismo en inglés, “flag” (hace cuarenta años así se llamaba, no sé ahora). Sirve para detectar cómo ha quedado el bucle después de haber probado los posibles divisores; si ningún resto es cero queda cargado con un 1, si no, con un cero y se rompe el bucle del interior de la función, momento en que salta fuera de ésta al bucle anidado para tomar el siguiente primo que usará como potencia para probar el siguiente candidato.

Saludos.

[mperdi]

Gracias a todos, acabo de obtener la solución. Gracias por el enlace, me ha servido porque también tenía que hacer una función con ello.
Gracias por la ayuda!!

[feriva]

Gracias a todos, acabo de obtener la solución. Gracias por el enlace, me ha servido porque también tenía que hacer una función con ello.
Gracias por la ayuda!!

De nada.

Éste no te lo puse porque tarda más; pero es más original y puede dar ideas para otros programas futuros que hagas:

Código: [Seleccionar]

import math #Se usa el módulo estándar de Python para matematicas.

def criba (n):

noprimos = set([])  # Defino un conjunto llamado noprimos.

for j in range(3, n+1,2):  # Bucle que recorre desde 3 hasta n de dos en dos (impares)

if j not in noprimos:  # Si j no esta en el conjunto... (j va a ser los primo)

Ex= float ( math.log(j+1)/math.log(2) ) # O sea, j = 2**Ex - 1 (forma de Mersenne)

if Ex == int(Ex): # Si el Exponente Ex y su parte entera coinciden, entonces es primo de Mersenne.

print (j)

noprimos.update(range(j*j, n+1, j)) # Va cargando los j en el conjunto desde su cuadrado y saltando de j en j
'''
Esto ultimo hace que no incluya a j pero si a todos sus multiplos en el conjunto. Al ir haciendolo con todos, incluye multiplos repetidos, pero la funcion set los saca de inmediato; lo considera literalmente como un conjunto, donde no existen elementos repetidos.
De esta manera, carga muchos menos elementos de los se cargaria en una lista normal, ahorrando mucha memoria.
Luego, si la rutina anterior comprueba que j no esta en el conjunto, entonces j tiene que ser primo; es tal cual la criba de Eratostenes.
'''
criba (1000000) # Con n=1000000 hace GOTO a la funcion par buscar entre ellos los posibles Mersenne.

Saludos.