Comment calculer les exposants des facteurs premiers pour un nombre donné?

Question

Je viens de terminer la 3ème question du projet Euler qui vous demande de trouver le plus grand facteur premier d'un nombre donné. J'ai fait une fonction qui retourne une liste de tous les facteurs premiers pour un nombre.

Par exemple, si vous entrez 100 il reviendriez [2.0, 5.0]

Je veux essayer de faire maintenant un programme qui retourne une liste avec les principaux facteurs qui apparaissent le même nombre de fois que leur exposant. Ainsi, par exemple, entrer 100 retournerait plutôt [2.0, 2.0, 5.0, 5.0] (parce que 100 est 2^2 * 5 * 2).

J'ai écrit une fonction qui le fait correctement si une liste contient les facteurs premiers et une liste contenant les exposants. Le problème est que la fonction que j'ai utilisée pour obtenir la liste des exposants est fausse.

Le code que j'ai écrit échoue pour certains nombres (18, 36, 50, 54 ...). Je suis assez nouveau à la programmation, donc si quelqu'un pouvait m'aider, je l'apprécierais vraiment.

def p_fctr_exp(n): 
    """Prime factorises n and gives the exponents of each factor""" 
    l1 = prime_factors(n) #Initialisation of variables and lists ('prime_factors()) is just the function I made which gives a list of the prime factors 
    p = 1 
    exp=[] 
    result=[] 
    for x in l1: #This multiplies the prime factors together just once 
     x = float(x) 
     p = (p * x) 
    for x in range(0,len(l1)): 
     """Loop which cycles through factors from smallest first and multiplies 
    the total by the factor until the point where one more would make it bigger 
    than the target number. The number of cycles required is stored in the 
    list 'exp'""" 
     a=1 
     while p<n: 
      p = p*float(l1[x]) 
      a+=1 
     if p == n: 
      exp.append(a) 
     elif x < len(l1)-1: 
      exp.append(a-1) 
    return exp 

Je pense que le problème se produit dans la boucle while puisqu'il fonctionne en multipliant le p du produit par le premier facteur le plus bas jusqu'à ce que cela devient trop grand, puis de passer au prochain facteur premier. Le problème est si l'exposant correct doit être 2, mais l'augmenter à 3 ne rend pas le produit plus grand que le nombre cible. J'ai l'impression que c'est probablement la mauvaise façon de résoudre le problème, mais je suis coincé sur ce qu'il faut changer.

Answer 1

Vous devriez utiliser l'opérateur modulo%. Dites que vous avez un nombre 270. Donc, vous divisez 270 par 3 jusqu'à ce qu'il soit "dépouillé" de 3, c'est à dire. n'a pas de facteurs de 3 à gauche.

• 270/3 = 90
• 90/3 = 30
• 30/3 = 10
• 10 n'est pas divisible par 3.

Ainsi, 270 = 10 * 3

vous en utilisant la fonction première de facteurs:

def p_fctr_exp(n): 
    primes = prime_factors(n) 
    exp=[] 

    for p in primes: 
     e=0 
      while (n%p==0): 
      n=n//p  # since p still divides n, 
      e+=1   # we divide n by p and increase the exponent 
     exp.append(e) 
    return exp 

Remarques

1. NE PAS utiliser flotte pour les problèmes de la théorie des nombres. Premièrement, l'opérateur modulo ne travaille pas dessus. Deuxièmement, vous ne savez jamais quand vous êtes victime d'une précision inexacte. Exemple: 0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1==1.0 évalue à False. Si vous devez vérifier la divisibilité, utilisez%.

2. Vous avez raison sur la raison pour laquelle votre code a échoué. Pour 18, prime_factors(18)=[2,3]. puisque 2 . Votre fonction rapporte que la puissance de 2 sur 18 est 4 ce qui est faux.

Answer 2

Puisque vous se demandaient si elle était la bonne façon de résoudre le problème, je vous suggère d'écrire une fonction similaire pour le calcul des facteurs principaux, ajoutant simplement chacun d'entre eux à la liste:

def prime_factors_list(n): 
    result = list() 
    diviser = 2 

    if n <= 0: 
     return [] #empty list 



    if n == 1: 
     return [1] 

    """We increment diviser when it does not divide n anymore""" 
    while n != 1: 
     if n % diviser == 0: # if 'diviser' divides n 
      n = n/diviser 
      result.append(diviser) # diviser works, we add it to the list 
     else: 
      diviser += 1 #diviser does not work, we try with a bigger one 

    return result 

Answer 3

Ceci fera le travail.

Il peut y avoir faster ways to do this que l'utilisation de la mémoire tradeoff pour cpu. Ici j'ai essayé de garder la liste des nombres premiers petite si cela suffit pour la factorisation.

import math 

class PrimeList(): 
    init_primes = [2,3,5,7,11,13,15,17,19,23] 
    def __init__(self, n): 
     self.primes = PrimeList.init_primes 
     self.extend(n) 

    def extend(self,n): 
     n = int(n) 
     nextnum = self.primes[-1] 
     while(self.primes[-1]<n): 
      nextnum += 2 
      if self.check(nextnum): 
       self.primes.append(nextnum) 

    def check(self,n): 
     n = int(n) 
     limit = int(math.sqrt(n)) 
     return all((n%p for p in self.primes if p<=limit)) 

    def is_prime(self, n): 
     n = int(n) 
     self.extend(int(math.sqrt(n))) 
     return self.check(n) 

    def factors(self, n): 
     n = int(n) 
     x = n 
     fact = dict() 
     for p in self.primes: 
      if p>x: 
       break 
      while x%p==0: 
       x = x/p 
       fact[p]=fact.get(p,0)+1 
     if x>1: 
      e = x if x!=n else int(math.sqrt(n)) 
      self.extend(e) 
      return self.factors(n) 
     return sorted(fact.items()) 



myprimes = PrimeList(25) 
print "cached primes:"+str(myprimes.primes) 
print "100 == "+str(myprimes.factors(100)) 
print "32768 == "+str(myprimes.factors(32768)) 
print "23! == "+str(myprimes.factors(math.factorial(23))) 
print "cached primes: "+str(myprimes.primes) 
print "10001 == "+str(myprimes.factors(10001)) 
print "cached primes:"+str(myprimes.primes) 

Sortie:

cached primes:[2, 3, 5, 7, 11, 13, 15, 17, 19, 23, 29] 
100 == [(2, 2), (5, 2)] 
32768 == [(2, 15)] 
23! == [(2, 19), (3, 9), (5, 4), (7, 3), (11, 2), (13, 1), (17, 1), (19, 1), (23, 1)] 
cached primes: [2, 3, 5, 7, 11, 13, 15, 17, 19, 23, 29] 
10001 == [(73, 1), (137, 1)] 
cached primes:[2, 3, 5, 7, 11, 13, 15, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137]