Générateur de Mersenne efficace en python

Question

J'ai fait un code qui ne semble pas très efficace. Il calcule seulement quelques-uns des nombres premiers.

Ceci est mon code:

num=float(1) 
a=1 

while(num>0): # Create variable to hold the factors and add 1 and itself (all numbers have these factors) 
    factors = [1, num] 

    # For each possible factor 
    for i in range(2, int(num/4)+3): 
     # Check that it is a factor and that the factor and its corresponding factor are not already in the list 
     if float(num) % i == 0 and i not in factors and float(num/i) not in factors: 
      # Add i and its corresponding factor to the list 
      factors.append(i) 
      factors.append(float(num/i)) 
    num=float(num) 
    number=num 
# Takes an integer, returns true or false 
    number = float(number) 
# Check if the only factors are 1 and itself and it is greater than 1 
    if (len(factors) == 2 and number > 1): 
     num2=2**num-1 
     factors2=[1, num] 
     for i in range(2, int(num2/4)+3): 
     # Check that it is a factor and that the factor and its corresponding factor are not already in the list 
      if float(num2) % i == 0 and i not in factors2 and float(num2/i) not in factors2: 
      # Add i and its corresponding factor to the list 
       factors2.append(i) 
       factors2.append(float(num2/i)) 
     if(len(factors2)==2 and num2>1): 
      print(num2) 
     a=a+1 
    num=num+2 

Comment puis-je faire mon code plus efficace et être en mesure de calculer rapidement le Mersenne nombres premiers. Je voudrais utiliser le programme pour trouver de nouveaux nombres parfaits possibles.

Answer 1

Toutes les solutions présentées jusqu'à présent utilisent des algorithmes mauvais, manque le point de nombres premiers Mersenne complètement. L'avantage des nombres premiers de Mersenne est que nous pouvons tester leur primalité plus efficacement que par la force brute comme les autres nombres impairs. Nous avons seulement besoin de vérifier un exposant pour primeness et utiliser un Lucas-Lehmer primality test pour faire le reste:

def lucas_lehmer(p): 
    s = 4 
    m = 2 ** p - 1 
    for _ in range(p - 2): 
     s = ((s * s) - 2) % m 
    return s == 0 

def is_prime(number): 
    """ 
    the efficiency of this doesn't matter much as we're 
    only using it to test the primeness of the exponents 
    not the mersenne primes themselves 
    """ 

    if number % 2 == 0: 
     return number == 2 

    i = 3 
    while i * i <= number: 
     if number % i == 0: 
      return False 
     i += 2 

    return True 

print(3) # to simplify code, treat first mersenne prime as a special case 

for i in range(3, 5000, 2): # generate up to M20, found in 1961 
    if is_prime(i) and lucas_lehmer(i): 
     print(2 ** i - 1) 

après M8 2147483647. tourbières de code de l'OP vers le bas après M7 524287 et @ code de FrancescoBarban embourbe Le code ci-dessus génère M18 dans environ 15 secondes! Voici jusqu'à M11, généré dans environ un quart de seconde:

3 
7 
31 
127 
8191 
131071 
524287 
2147483647 
2305843009213693951 
618970019642690137449562111 
162259276829213363391578010288127 
170141183460469231731687303715884105727 
6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151 
531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127 

Ce programme embourbe ci-dessus M20, mais ce n'est pas une mise en œuvre efficace particulary. Ce n'est tout simplement pas un mauvais algorithme.

Answer 2

import math 

def is_it_prime(n): 

    # n is already a factor of itself 
    factors = [n] 

    #look for factors 
    for i in range(1, int(math.sqrt(n)) + 1): 

     #if i is a factor of n, append it to the list 
     if n%i == 0: factors.append(i) 
     else: pass 

    #if the list has more than 2 factors n is not prime 
    if len(factors) > 2: return False 
    #otherwise n is prime 
    else: return True 

n = 1 
while True: 

    #a prime P is a Mersenne prime if P = 2^n - 1 
    test = (2 ** n) - 1 

    #if test is prime is also a Mersenne prime 
    if is_it_prime(test): 
     print(test) 
    else: pass 
    n += 1 

probablement il sera collé à 2.147.483.647, mais vous savez, le prochain premier de Mersenne est 2305843009213693951 ... alors ne vous inquiétez pas si cela prend plus de temps que prévu;)

Answer 3

Si vous voulez juste pour vérifier si un nombre est premier, alors vous n'avez pas besoin de trouver tous ses facteurs. Vous savez déjà 1 et num sont des facteurs. Dès que vous trouvez un troisième facteur, le nombre ne peut pas être premier. Vous perdez du temps à chercher les facteurs quatrième, cinquième etc. Un nombre Mersenne est de la forme 2^n - 1, et est donc toujours impair. Par conséquent, tous ses facteurs sont étranges. Vous pouvez réduire de moitié le temps d'exécution de votre boucle si vous recherchez uniquement les facteurs impairs: commencez par 3 et l'étape 2 par le facteur suivant. Les facteurs viennent par paires, une plus grande que la racine carrée et une plus petite. Par conséquent, il suffit de rechercher des facteurs jusqu'à la racine carrée, comme le montre le code de Francesco. Cela peut vous donner un gain de temps important pour les grands nombres de Mersenne.

Mettre ces deux points ensemble, votre boucle devrait être plus comme:

#look for factors 
for i in range(3, int(math.sqrt(n)) + 1, 2):